题解 P5888 【传球游戏】
【题目大意】
有n个人，球1一开始在1号手中，每次持球者可以传递给其它人，但是有限制条件，某些传球方式是不可行的，求经过m次传球后，球回到1号手中的方案数
【分析】
这道题是由部分分到AC的典范
不妨从部分分入手，想正解
签到分：10分
k=0,也就是所有人都能互相传球
我们把除1号外的人统称为“其它人”
那么场上只有2类人，1号和其它人，除了1号，其它人都是相同的
开几个变量记录一下当前传到1号和其它人的方案数即可
LL lst1=1,lst2=0,now1,now2;
//lst表示上一次分别在两类人手中的方案数
//now表示当前在两类人手中的方案数
//now2单指1个人
while(m--){
now1=lst2*(n-1)%TT;
//其它n-1个其它人都可以传给1号
now2=(lst2*(n-2)+lst1)%TT;
//除1号和自己的n-2个人可以传给其它人，1号也可以给其它人
lst1=now1,lst2=now2;
//传递
}
printf("%lld\n",now1);
return 0;第一部分：15分
很明显这是一个经典DP
f[i][j]表示第i轮传给j号的方案数
转移方程：f[i][j]+=f[i-1][k]，前提k可以传给j
复杂度O（n n m）
第二部分：35分
之前的DP是枚举所有能传给自己的人
可以换个思路，统计上一轮所有传递方案，减去不能传给自己的人的方案
f[0][1]=1;
for(int i=1;i<=m;i++){
int sum=0;
//sum是上一轮总方案
for(int j=1;j<=n;j++) sum=(sum+f[i-1][j])%TT;
for(int j=1;j<=n;j++){
f[i][j]=(sum-f[i-1][j]+TT)%TT;
//自己不能传给自己，先减掉自己
for(int k=lnk[j];k;k=e[k].nxt){
int y=e[k].to;
if(y==j) continue;
//避免重复减自己
f[i][j]=(f[i][j]-f[i-1][y]+TT)%TT;
//枚举不能传的，再从总方案中减去
}
}
}复杂度O（n* m）
第三部分：55分
k的限制暂时还没有什么想法...
第四部分：100分
n规模庞大，然而k却相对较小
联系签到分的思路，就能发现解题关键
k最大5e+4，也就是说有传递限制的至多只有1e+5个人
那么剩下的999900000个人呢？
只需要计算一次就够了
我们依旧称这999900000个人为“其它人”
同样可以借助几个变量表示，转移方程与第二部分差不多
f[0][1]=1;
RE LL el=0;
for(RE int i=1;i<=m;i++){
RE bool A=i&1,B=1-A;
//数据比较大，滚动一下，A是当前，B是之前
RE LL sum=0,now=el*(n-num-1)%TT;
//el和now是其它人的信息，sum是牵扯到的人的信息
for(RE int j=1;j<=num;j++){
//此处num是限制条件牵扯到的人
sum+=f[B][j];
f[A][j]=0;
}
sum%=TT;
(now+=sum)%=TT;
(sum+=el*(n-num)%TT)%=TT;
for(RE int j=1;j<=num;j++){
f[A][j]=(sum-f[B][j]+TT)%TT;
for(RE int k=lnk[j];k;k=e[k].nxt){
RE int y=e[k].to;
if(y==j) continue;
f[A][j]+=-f[B][y]+TT;
}
f[A][j]%=TT;
}
el=now;
}复杂度 O（k* m）
所以AC=签到分+35分部分分
【代码】
#include<bits/stdc++.h>
#define LL long long
#define IN inline
#define RE register
using namespace std;
const int maxn=1e5+5,maxm=205,TT=998244353;
int n,m,k;
int tot,lnk[maxn];
LL f[2][maxn];
int c[maxn],cnt,d[maxn],num;
struct edge{
int to,nxt;
}e[maxn];
struct why{
int x,y;
}a[maxn];
IN int read(){
RE int t=0,f=1;RE char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') t= t*10+ch-'0',ch=getchar();
return t*f;
}
IN void add_e(RE int x,RE int y){
e[++tot]=(edge){y,lnk[x]};
lnk[x]=tot;
}
IN int find(RE int x){
RE int L=1,R=num,mid;
while(L<=R){
mid=L+R>>1;
if(d[mid]==x) return mid;
if(x<d[mid]) R=mid-1;
else L=mid+1;
}
}
int main(){
freopen("P5888.in","r",stdin);
freopen("P5888.out","w",stdout);
n=read(),m=read(),k=read();
c[++cnt]=1;
for(RE int i=1;i<=k;i++){
RE int x=read(),y=read();
a[i].x=x,a[i].y=y;
c[++cnt]=x,c[++cnt]=y;
}
sort(c+1,c+1+cnt);
d[num=1]=1;
for(RE int i=2;i<=cnt;i++){
if(c[i]!=c[i-1]) d[++num]=c[i];
}
for(RE int i=1;i<=k;i++){
RE int x=find(a[i].x),y=find(a[i].y);
add_e(y,x);
}
//离散操作，把杂乱的编号看成1~num
f[0][1]=1;
RE LL el=0;
for(RE int i=1;i<=m;i++){
RE bool A=i&1,B=1-A;
RE LL sum=0,now=el*(n-num-1)%TT;
for(RE int j=1;j<=num;j++){
sum+=f[B][j];
f[A][j]=0;
}
sum%=TT;
(now+=sum)%=TT;
(sum+=el*(n-num)%TT)%=TT;
for(RE int j=1;j<=num;j++){
f[A][j]=(sum-f[B][j]+TT)%TT;
for(RE int k=lnk[j];k;k=e[k].nxt){
RE int y=e[k].to;
if(y==j) continue;
f[A][j]+=-f[B][y]+TT;
}
f[A][j]%=TT;
}
el=now;
}
printf("%lld\n",f[m&1][1]);
return 0;
}【总结】
从局部到整体，循序渐进