Burnside引理&Polya定理-置换群-学习笔记

[远古时期写的博客](https://www.luogu.org/blog/i207M/burnside-yin-li-polya-ding-li-xue-xi-bi-ji) 主要是毕克的讲课内容 ### Lucas数 长度为n的环，选一些点，两两不相邻的方案数。$L[0]=2,L[1]=1,L[n]=L[n-1]+L[n-2]$ #### HDU 5868,POJ 2888 矩阵乘法 #### BZOJ 1004 DP ### [SHOI2006]有色图 ```cpp int md; il int qpow(int a,int b) { int res=1; for(; b; b>>=1,a=(LL)a*a%md) if(b&1) res=(LL)res*a%md; return res; } int n,m; int tot; int num[100],cnt[100],tp; il int gcd(int a,int b) { ri t; while(b) t=a,a=b,b=t%b; return a; } int fac[100],inv[100],ifac[100]; void prework() { fac[0]=ifac[0]=fac[1]=ifac[1]=inv[1]=1; for(ri i=2; i<=60; ++i) fac[i]=(LL)fac[i-1]*i%md,inv[i]=(LL)(md-md/i)*inv[md%i]%md; for(ri i=2; i<=60; ++i) ifac[i]=(LL)ifac[i-1]*inv[i]%md; } int calc() { int ans=0; for(ri i=1; i<=tp; ++i) ans=(ans+(LL)num[i]/2*cnt[i])%md; for(ri i=1; i<=tp; ++i) { for(ri j=i+1; j<=tp; ++j) { ans=(ans+(LL)cnt[i]*cnt[j]*gcd(num[i],num[j]))%md; } ans=(ans+(LL)cnt[i]*(cnt[i]-1)/2*num[i])%md; } ans=qpow(m,ans); int ci=fac[n]; for(ri i=1; i<=tp; ++i) ci=(LL)ci*qpow(inv[num[i]],cnt[i])%md*ifac[cnt[i]]%md; tot=(tot+ci)%md; return (LL)ans*ci%md; } int ans; void dfs(int r) { if(!r) { ans=(ans+calc())%md; return; } for(ri v=num[tp]-1; v>=2; --v) { int x=r-v,t=++tp; num[t]=v,cnt[t]=1; for(; x>=0; x-=v,++cnt[t]) dfs(x); --tp; } num[++tp]=1,cnt[tp]=r; dfs(0); --tp; } int solve() { num[0]=n+1; dfs(n); return (LL)ans*qpow(tot,md-2)%md; } signed main() { #ifdef M207 freopen("in.in","r",stdin); // freopen("out.out","w",stdout); #endif in(n,m,md); prework(); out(solve()); return 0; } ``` ### Codechef ADIMAT 如果一个矩阵能通过首先任意改变行的顺序，再任意改变列的顺序，从而变成另一个矩阵，那么这两个矩阵相同，而相同的矩阵只应当被计算一次。 由于答案可能很大，请输出答案对10^9 + 7 取模的结果。 先枚举两维中较小的一维（<23），然后枚举它的整数划分（就是轮换），然后对于另一维的划分，使用DP求出总方案。 这里我用的方法和毕克上课说的不太一样，没有使用去重的完全背包，而是直接计算： $dp[i]$表示已经处理了i个位置的贡献。每次枚举最后一个位置和几个数组成一组$C^{j-1}_{i-1}$，这一组内的情况（圆排列$(j-1)!$），两部分的贡献$g[j]\times dp[i-j]$ 其中，$g[i]$的计算方法是：和行的每一个轮换形成了若干个矩形，每个矩形内的轨道数为$gcd(i,j)$ ```cpp int calc() { for(ri i=1; i<=m; ++i) { int val=1; for(ri j=1; j<=tp; ++j) val=(LL)val*qpow(2,gcd(i,num[j])*cnt[j])%md; g[i]=val; } for(ri i=1; i<=m; ++i) { int tot=0; for(ri j=1; j<=i; ++j) tot=(tot+(LL)c[i-1][j-1]*fac[j-1]%md*g[j]%md*dp[i-j]%md)%md; dp[i]=tot; } int ci=fac[n]; for(ri i=1; i<=tp; ++i) ci=(LL)ci*ifac[cnt[i]]%md*qpow(inv[num[i]],cnt[i])%md; return (LL)dp[m]*ci%md; } ``` *以下为毕克在WC时的讲课内容* ### Problem1 Path 在一个 n×n 的网格中，从左下角到右上角，每次向上或者向右 走一格，一共需要向右走 n 次，向上走 n 次。输入 n(1 ≤ n ≤ 10^6)，问本质不同的方案有多少种。结果对 p = 10^9 + 9 取模。 如果两个方案可以通过对称和旋转变成相同的，我们认为他们本质相同。 将路径变为01串，第一个操作是01取反，第二个操作是将字符串翻转 分类讨论4种情况即可。 不动：$2n\choose n$ 翻转：${n \choose n/2}[n\mod 2=0]$ 取反：0 翻转且取反：$2^n$ ### Problem 6 Wool 吕欣寒假讲的。