1 条题解

  • 0
    @ 2025-10-8 17:02:15
    #include <bits/stdc++.h>
    using namespace std;
    template <typename T> void qread(T &x){
    	x=0; int f=1; char c=getchar();
    	for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
    	for(; isdigit(c); c=getchar()) x=x*10+(c-'0');
    	x*=f;
    }
    typedef long long LL;
    const int N=110;
    int sr, sb, sg, n;
    int a[N], len, sz[N];
    LL P, f[N][N][N];
    bool v[N];
    LL calc(){
    	memset(v, 0, sizeof(v));
    	len=0; memset(sz, 0, sizeof(sz));
    	for(int i=1; i<=n; i++) if(!v[i]){
    		len++; int p=i;
    		while(!v[p]){
    			v[p]=1; 
    			sz[len]++;
    			p=a[p];
    		}
    	}
    	memset(f, 0, sizeof(f));
    	f[0][0][0]=1;
    	for(int si=1; si<=len; si++){
    		for(int i=sr; i>=0; i--){  //***注意!!这里每个轮换只能计数一次,所以要倒着遍历 
    			for(int j=sb; j>=0; j--){
    				for(int k=sg; k>=0; k--){
    					if(i>=sz[si]) f[i][j][k]=(f[i][j][k]+f[i-sz[si]][j][k])%P;
    					if(j>=sz[si]) f[i][j][k]=(f[i][j][k]+f[i][j-sz[si]][k])%P;
    					if(k>=sz[si]) f[i][j][k]=(f[i][j][k]+f[i][j][k-sz[si]])%P;
    				}
    			}
    		}
    	}
    	return f[sr][sb][sg];
    }
    LL qpow(LL a, LL b){
    	LL res=1;
    	while(b){
    		if(b&1) res=res*a%P;
    		a=a*a%P; b/=2;
    	}
    	return res;
    }
    int main(){
    	qread(sr); qread(sb); qread(sg);
    	int m; qread(m); qread(P);
    	n=sr+sb+sg;
    	LL ans=0;
    	for(int i=1; i<=m; i++){
    		for(int j=1; j<=n; j++) qread(a[j]);
    		ans=(ans+calc())%P;
    	}
    	for(int i=1; i<=n; i++) a[i]=i;  //不要忘了恒等变换 
    	ans=(ans+calc())%P;
    	
    	ans=ans*qpow(m+1, P-2)%P; //加上恒等变换 
    	printf("%lld\n", ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    2657
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    10
    已通过
    6
    上传者