社区讨论

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 条回复,欢迎继续交流。

正在加载回复...