[破碎的状态] [-19] BZOJ 1004
这一题是Burnside引理的复习..
这一题根据Burnside..
除了要手动写个dp..求Burnside的东西..
思考了半天发现数据范围这么小为啥不dp..
PS:这是第三次过这题了..
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<time.h> #include<math.h> #include<memory> #include<vector> #include<bitset> #include<fstream> #include<stdio.h> #include<utility> #include<sstream> #include<string.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; int sr,sb,sg; int dp[25][25][25]; int n; int modo; int a[65]; void trys_dp(int n,int y) { int r,b,g; for (r=0;r<=n;r++) { if (r>sr) continue; for (b=0;r+b<=n;b++) { if (b>sb) continue; g=n-r-b; if (g>sg) continue; if (r>=y) dp[r][b][g]+=dp[r-y][b][g]; if (b>=y) dp[r][b][g]+=dp[r][b-y][g]; if (g>=y) dp[r][b][g]+=dp[r][b][g-y]; dp[r][b][g]%=modo; } } } int power(int x,int y) { if (y==0) return 1; int t=power(x,y/2); t=t*t%modo; if (y%2==1) t=t*x%modo; return t; } int main() { #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif scanf("%d%d%d",&sr,&sb,&sg); n=sr+sb+sg; int m; scanf("%d",&m); scanf("%d",&modo); int i; int ans=0; for (i=0;i<=m;i++) { int j; for (j=0;j<n;j++) { scanf("%d",&a[j]); a[j]--; if (i==m) a[j]=j; } memset(dp,0,sizeof(dp)); dp[0][0][0]=1; int now=0; for (j=0;j<n;j++) { if (a[j]!=-1) { int x=j; int sum=0; for (;;) { int temp=a[x]; a[x]=-1; x=temp; sum++; if (x==j) break; } now+=sum; trys_dp(now,sum); } } ans+=dp[sr][sb][sg]; } printf("%d\n",ans*power(m+1,modo-2)%modo); return 0; }