社区讨论
WA 40分,不知道什么原因,求助
P5888 传球游戏参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m6grntbh
- 此快照首次捕获于
- 2025/01/29 01:43 去年
- 此快照最后确认于
- 2025/11/04 10:12 4 个月前
CPP
#include<iostream>
#include<algorithm>
using namespace std;
#define mod 998244353
#define ll long long
struct node {
int a, b;
};
node arr[50005];
int b[100005];
int cnt;
ll dp[100005],f[100005];//滚动数组
int main() {
int n, m, k;
cin >> n >> m >> k;
bool ff = 0;
for (int i = 1; i <= k; i++) {
cin >> arr[i].a >> arr[i].b;
if (arr[i].a == 1 || arr[i].b == 1)ff = 1;
b[++cnt] = arr[i].a;
b[++cnt] = arr[i].b;
}
sort(b + 1, b + 1 + cnt);
cnt = unique(b + 1, b + 1 + cnt) - (b + 1);
//离散化
for (int i = 1; i <= k; i++) {
arr[i].a = lower_bound(b + 1, b + cnt + 1, arr[i].a) - b;
arr[i].b = lower_bound(b + 1, b + cnt + 1, arr[i].b) - b;
}
//1-cnt是单个人,第cnt+1是其余人
dp[1] = 1;
if (!ff)cnt++;//1如果没有纳入过限制,1不能沦为自由人
for (int i = 1; i <= m; i++) {//m轮传球
ll tot = 0;
for (int j = 1; j <= cnt + 1; j++) {
f[j] = dp[j];//存储上一轮的方案数
tot = (tot + f[j]) % mod;//记录上一轮的方案总数
}
tot = (tot + ((n - cnt - 1) * f[cnt + 1]) % mod) % mod;
//默认都能传,所以上轮总方案数是这轮每个人的方案数
for (int j = 1; j <= cnt + 1; j++) {
dp[j] = (tot - f[j] + mod) % mod;//但有一对默认限制,自己不能传给自己
}
for (int j = 1; j <= k; j++) {//处理限制
if (arr[j].a != arr[j].b)dp[arr[j].b] = (dp[arr[j].b] - f[arr[j].a] + mod) % mod;//a不能传给b
}
}
cout << dp[1];
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...