自动搬运

查看原文

来自洛谷，原作者为

	破忆 一个loser而已

搬运于2025-08-24 22:15:18，当前版本为作者最后更新于2020-01-01 18:54:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

【题目大意】

有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;
}

---

【总结】

从局部到整体，循序渐进