题目：
学习材料：
bzoj 1004：这道题注意考虑单位元的那个置换。
然后用 polya 定理即可。不动点个数是 dp 出来的，以保证合法。 dp 时注意 res -= tot 。
#include#include #include #include #define ll long longusing namespace std;const int N=65,M=25;int n,m,mod,s0,s1,s2,a[N],f[N],dp[2][M][M][M],ans;bool vis[N];void upd(int &x){x>=mod?x-=mod:0;}int pw(int x,int k){ int ret=1;while(k){ if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}int solve(){ memset(vis,0,sizeof vis); memset(dp[0],0,sizeof dp[0]); dp[0][s0][s1][s2]=1; bool fx=0; int res=n; for(int i=1;i<=n;i++) if(!vis[i]) { int tot=0,cr=i; while(!vis[cr]) { tot++; vis[cr]=1; cr=a[cr]; } bool tf=!fx; memset(dp[tf],0,sizeof dp[tf]); for(int x0=s0;x0>=0;x0--) for(int x1=s1;x1>=0;x1--) { int x2=res-x0-x1,d; if(x2>s2||!(d=dp[fx][x0][x1][x2]))continue; if(x0>=tot)dp[tf][x0-tot][x1][x2]+=d,upd(dp[tf][x0-tot][x1][x2]); if(x1>=tot)dp[tf][x0][x1-tot][x2]+=d,upd(dp[tf][x0][x1-tot][x2]); if(x2>=tot)dp[tf][x0][x1][x2-tot]+=d,upd(dp[tf][x0][x1][x2-tot]); } fx=tf; res-=tot; } return dp[fx][0][0][0];}int main(){ scanf("%d%d%d%d%d",&s0,&s1,&s2,&m,&mod); n=s0+s1+s2; for(int j=1;j<=n;j++)a[j]=j; ans+=solve(); upd(ans); for(int i=1;i<=m;i++) { for(int j=1,d;j<=n;j++)scanf("%d",&d),a[d]=j; ans+=solve(); upd(ans); } ans=(ll)ans*pw(m+1,mod-2)%mod; printf("%d\n",ans); return 0;}
poj 2409：polya模板。
#include#include #include #include #define ll long longusing namespace std;const int N=35;int n,m; ll ans;int gcd(int a,int b){ return b?gcd(b,a%b):a;}ll pw(ll x,int k){ll ret=1;while(k){ if(k&1)ret*=x;x*=x;k>>=1;}return ret;}int main(){ while(1) { scanf("%d%d",&m,&n);if(!n&&!m)return 0; ans=0; for(int i=1;i<=n;i++)ans+=pw(m,gcd(n,i)); if(n&1) ans+=n*pw(m,n+1>>1); else ans+=(n*pw(m,n>>1)>>1)+(n*pw(m,(n>>1)+1)>>1); printf("%lld\n",ans/(n<<1)); } return 0;}