自动搬运

查看原文

来自洛谷，原作者为

	Acoipp We shall never surrender!

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

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

以下是正文

首先考虑给的集合 $S$ 到达 $T$，有一些点的位置会发生变化，设有 $l$ 个，那么剩下 $k-l$ 个没有发生变化，那么有结论 $S \to T$ 的方案数只跟 $l$ 有关。

这个方案可以直接矩阵乘法求出来，设矩阵为 $B$，那么 $B$ 的构造是容易的，只需要设置一个阈值 $K$，预处理出 $B^0 \sim B^K$ 以及 $B^K,B^{2K},\dots$ 就可以实现 $O(k^2)$ 查询出来在 $T$（题面中的意思）固定的情况下每个 $l$ 的方案数。

这一部分预处理时间复杂度是 $O(\sqrt{mod}k^3+k^2q)$ 的。

然后考虑处理出 $f_{S,i}$ 表示与集合 $S$ 中不同的元素（某个物品在 $S$ 中的位置与在 $T$ 中的位置不一样）有 $i$ 个的 $T$ 的所有得分之和。

这个 $f$ 我们可以用类似于高维前缀和的方法处理，大概就是枚举 $i$，然后 $f_{S,j}$ 存的是所有 $T$ 与 $S$ 在前 $i$ 位有 $j$ 个不同，并且后 $k-i$ 位与 $S$ 完全相同的 $T$ 的得分之和。

最后只需要枚举第 $i+1$ 位填的是什么即可。

于是就可以用高维前缀和的套路优化了，这部分的时间复杂度是 $O(n^kk^2)$。

整体来说呢，需要卡卡常才能过。

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define mod 998244353
using namespace std;
ll n,k,q,i,j,l,l2,up,val[N],qm[N],ans=1,a,b,anss[21][21],temp[21][21],g[N][21],h[N][21],p[21],inv[21],C[25][25],B,ps;
int f[32005][21][21],f2[32005][21][21];
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
inline void times(ll a[21][21],int b[21][21],ll n1,ll n2,ll n3){
	for(ll i=0;i<=n1;i++) for(ll j=0;j<=n2;j++) for(ll k=0;k<=n3;k++) temp[i][k]=(temp[i][k]+a[i][j]*b[j][k])%mod;
	for(ll i=0;i<=n1;i++) for(ll k=0;k<=n3;k++) a[i][k]=temp[i][k],temp[i][k]=0;
}
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0,w = 1;
	char c = nc();
	while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res*w;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
int main(){
	n=read(),k=read(),q=read(),up=qmi(n,k,mod),B=sqrt(mod);
	qm[0]=1;
	for(i=1;i<=k;i++) qm[i]=qm[i-1]*n;
	for(i=0;i<up;i++) val[i]=read(),g[i][0]=val[i];
	for(i=0;i<k;i++){
		for(j=0;j<up;j++){
			for(l=0;l<=i;l++){
				(h[j][l] = (h[j][l]+g[j][l]))>=mod&&(h[j][l]-=mod);
				(h[j][l+1] = (h[j][l+1]-g[j][l]))<0&&(h[j][l+1]+=mod);
			}
			if((j/qm[i])%n==0){
				memset(p,0,sizeof(p));
				for(l=0;l<n;l++) for(l2=0;l2<=i;l2++) (p[l2+1]=(p[l2+1]+g[j+l*qm[i]][l2]))>=mod&&(p[l2+1]-=mod);
				for(l=0;l<n;l++) for(l2=0;l2<=i+1;l2++) (h[j+l*qm[i]][l2]=(p[l2]+h[j+l*qm[i]][l2]))>=mod&&(h[j+l*qm[i]][l2]-=mod);
			}
		}
		for(j=0;j<up;j++) for(l=0;l<=i+1;l++) g[j][l]=h[j][l],h[j][l]=0;
	}
	C[0][0]=1;
	for(i=0;i<=k;i++){
		for(j=0;j<=k;j++){
			if(i) C[i][j]+=C[i-1][j];
			if(i&&j) C[i][j]+=C[i-1][j-1];
			if(C[i][j]>=mod) C[i][j]-=mod;
		}
	}
	for(i=0;i<=k;i++){
		if(i) f[1][i][i-1]=(f[1][i][i-1]+i)%mod,f[1][i][i]=(f[1][i][i]+1ll*i*(n-2))%mod;
		if(k-i) f[1][i][i+1]=(f[1][i][i+1]+1ll*(k-i)*(n-1))%mod;
	}
	for(i=2;i<=B;i++){
		for(j=0;j<=k;j++) for(l=0;l<=k;l++) for(ps=0;ps<=k;ps++) f[i][j][ps]=(f[i][j][ps]+1ll*f[i-1][j][l]*f[1][l][ps])%mod;
	}
	for(i=0;i<=k;i++) for(j=0;j<=k;j++) f2[1][i][j]=f[B][i][j];
	for(i=2;i<=(mod/B);i++){
		for(j=0;j<=k;j++) for(l=0;l<=k;l++) for(ps=0;ps<=k;ps++) f2[i][j][ps]=(f2[i][j][ps]+1ll*f2[i-1][j][l]*f2[1][l][ps])%mod;
	}
	for(i=0;i<=k;i++) inv[i]=qmi(C[k][i],mod-2,mod)*qmi(qmi(n-1,i,mod),mod-2,mod)%mod;
	while(q--){
		a=read(),b=read();
		b=b*ans%mod;
		for(i=0;i<=k;i++) anss[0][i]=0;
		anss[0][0]=1;
		if(b/B) times(anss,f2[b/B],0,k,k);
		if(b%B) times(anss,f[b%B],0,k,k);
		for(i=0,ans=0;i<=k;i++) ans=(ans+anss[0][i]*g[a][i]%mod*inv[i])%mod;
		write(ans),pc('\n');
	}
	return fwrite(obuf,p3-obuf,1,stdout),0;
}