P6712 [THUPC2019] 摆家具 题解

· · 题解

首先考虑给的集合 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;
}