题解 P5888 【传球游戏】
cdcq
2020-01-01 18:34:56
性质：
人数虽然有1e9，但是每条边只限制两个人，被限制的人最多有1e5个，剩下的都是自由人，他们的方案数都完全相同，可以用一个数统一表示
转化问题：
正难则反，直接建完全图模拟传球复杂度太高，那就考虑由总方案减去不合法的
需要注意到每次传球，假设总方案数容易求出，那么需要减去的不合法传球方法等于边的个数，而边的个数只有5e4
接下来考虑求总方案数
每一个人接到球的总方案数就是剩余所有人上一轮的方案数之和，因为在上一轮的每个方案的基础上把求传给这个人就可以得到新的方案
这个可以由上一轮每个人的方案数之和减去上一轮自己的方案数快速求出
至此问题解决
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int mo=998244353;
struct edg{int y,nxt;}e[51000]; int lk[110000],ltp=0;
void ist(int x,int y){ e[++ltp]=(edg){y,lk[x]}; lk[x]=ltp;}
struct nds{int x,y;}a[51000];
int n,m,o;
int q[110000],hd=0;
int c[110000],ctp=0;
LL f[2][110000];
int bnrsch(int x){
int l=1,r=ctp,md;
while(l+1<r){
md=(l+r)>>1;
(c[md]<x ? l : r)=md;
}
return c[l]==x ? l : r;
}
int main(){
cin>>n>>m>>o;
for(int i=1;i<=o;++i){
scanf("%d%d",&a[i].x,&a[i].y);
q[++hd]=a[i].x,q[++hd]=a[i].y;
}
sort(q+1,q+hd+1);
for(int i=1;i<=hd;++i)if(q[i]!=q[i-1])
c[++ctp]=q[i];
for(int i=1;i<=o;++i)if(a[i].y!=a[i].x)
ist(bnrsch(a[i].y),bnrsch(a[i].x));
if(c[1]!=1){
c[++ctp]=1;
f[0][ctp]=1;
}
else f[0][1]=1;
for(int i=1;i<=m;++i){
LL bwl=0;
for(int j=1;j<=ctp;++j) bwl=(bwl+f[(i-1)&1][j])%mo;
bwl=(bwl+f[(i-1)&1][0]*(n-ctp))%mo;
for(int j=0;j<=ctp;++j){
f[i&1][j]=(bwl-f[(i-1)&1][j])%mo;
for(int k=lk[j];k;k=e[k].nxt) f[i&1][j]=(f[i&1][j]-f[(i-1)&1][e[k].y])%mo;
}
}
printf("%lld\n",(f[m&1][(c[1]==1 ? 1 : ctp)]%mo+mo)%mo);
return 0;
}
```