题目大意
有一个 \(n\) 个点的环，你要用 \(m\) 中颜色染这 \(n\) 个点。
要求连续 \(m\) 个点的颜色不能是 $1 \sim m $ 的排列。
两种环相同当且仅当这两个环可以在旋转之后变得一模一样。
求方案数对 \({10}^9+7\) 取模的结果。
\(n\leq {10}^9,m\leq 7\)
题解
考虑 polya 定理，记 \(f(n)\) 为 \(n\) 个点的答案，\(g(n)\) 为 \(n\) 个点不考虑旋转的答案。那么就有
\[ \begin{align} f(n)&=\frac{1}{n}\sum_{i=1}^ng(\gcd(n,i))\\ &=\frac{1}{n}\sum_{i\mid n}\varphi(\frac{n}{i})g(i) \end{align} \] \(g(i)\) 可以 DP 计算。记 \(h_{i,j,k}\) 为长度为 \(i\) 的链，前 \(m\) 个点的状态（颜色）为 \(j\)，最后 \(m\) 个点的状态为 \(k\) 的方案数。
还可以记录前 \(m\) 个颜色的前多少个是互不相同的，还有最后 \(m\) 个点的颜色。就前 \(j\) 个的颜色是互不相同的，第 \(j+1\) 个点颜色和前面某个点颜色相同。
显然 \(g(i)\) 有一个长度不超过 \(m^m\) 的递推式。
暴力打出前面的项然后 BM 求出递推式即可。
开 O2 只用了 48s 就打出来了。
\(m=7\) 时递推式长度为 \(409\)。
表在这：
代码
const int N=1010;const ll p=1000000007;ll fp(ll a,ll b){ ll s=1; for(;b;b>>=1,a=a*a%p) if(b&1) s=s*a%p; return s;}ll b[10][2010]=表;ll a[10][2010]=表;int c[N],d[N],t;ll pw[N][N];ll ans;int n,m;int s[N];int len;void add(int &a,ll b){ a=(a+b)%p;}void mul(){ static int f[N]; for(int i=0;i<=2*len;i++) f[i]=0; for(int i=0;i<=len;i++) if(s[i]) for(int j=0;j<=len;j++) add(f[i+j],(ll)s[i]*s[j]); for(int i=0;i<=2*len;i++) s[i]=f[i];}void module(){ for(int i=2*len;i>=len;i--) if(s[i]) { for(int j=1;j<=len;j++) add(s[i-j],(ll)s[i]*b[m][j]); s[i]=0; }}void fp(int x){ if(!x) { for(int i=0;i<=2*len;i++) s[i]=0; s[0]=1; return; } fp(x>>1); mul(); if(x&1) { for(int i=2*len;i>=1;i--) s[i]=s[i-1]; s[0]=0; } module();}ll calc(int x){ if(x<=500) return a[m][x]; fp(x-1); ll res=0; for(int i=1;i<=len;i++) res=(res+(ll)a[m][i]*s[i-1])%p; return res;}void dfs(int x,int y,ll phi){ if(x>t) { ans=(ans+calc(y)*phi)%p; return; } for(int i=0;i 1) { c[++t]=_n; d[t]=1; } for(int i=1;i<=t;i++) { pw[i][0]=1; for(int j=1;j<=d[i];j++) pw[i][j]=pw[i][j-1]*c[i]%p; } len=b[m][0]; dfs(1,1,1); ans=ans*fp(n,p-2)%p; ans=(ans%p+p)%p; printf("%lld\n",ans); return 0;} 打表程序
const ll p=1000000007;const int N=1010;const int n=1000;//const int m=5;int m;ll fp(ll a,ll b){ ll s=1; for(;b;b>>=1,a=a*a%p) if(b&1) s=s*a%p; return s;}const int MA=2100000;int e[MA];int ban[MA];vector g[N];int pw[N];int ma;namespace gao1{ int a[N],b[N],c[N]; void dfs(int x) { if(x>m) { for(int i=1;i<=m;i++) b[i]=0; int tot=0; int s=0; int s2=0; int first=0; for(int i=1;i<=m;i++) { if(!b[a[i]]) b[a[i]]=++tot; c[i]=b[a[i]]; s+=c[i]*pw[i-1]; s2+=a[i]*pw[i-1]; if(c[i]<=c[i-1]&&!first) first=i-1; } if(tot==m) ban[s2]=1; else g[first].push_back(s); return; } for(int i=1;i<=m;i++) { a[x]=i; dfs(x+1); } } void gao() { dfs(1); }}namespace gao2{ int a[N],b[N],c[N]; void dfs(int x) { if(x>m) { for(int i=1;i<=m;i++) b[i]=0; for(int i=m;i>=1;i--) if(!a[i]||!b[a[i]]) { c[i]=a[i]; b[a[i]]=1; } else c[i]=0; int s=0,s1=0; for(int i=1;i<=m;i++) s+=c[i]*pw[i-1]; for(int i=1;i<=m;i++) s1+=a[i]*pw[i-1]; e[s1]=s; return; } for(int i=0;i<=m;i++) { a[x]=i; dfs(x+1); } } void gao() { dfs(1); }}int f[N];int h[2][MA];int d[MA];void add(int &a,int b){ a=(a+b)%p;}int append(int a,int b){ return a/(m+1)+b*pw[m-1];}namespace gao3{ void gao(int x) { memset(d,0,sizeof d); for(int i=0;i<=ma;i++) { int flag=1; for(int y=i,j=1;j<=x;j++) { y=append(y,j); if(ban[y]) { flag=0; break; } } d[i]=flag; } memset(h,0,sizeof h); int cur=0; for(auto v:g[x]) h[cur][e[v]]++; for(int i=m;i<=n;i++) { fprintf(stderr,"%d %d %d\n",m,x,i); memset(h[cur^1],0,sizeof h[cur^1]); for(int j=0;j<=ma;j++) if(h[cur][j]&&!ban[j]) { add(f[i],d[j]*h[cur][j]); for(int k=1;k<=m;k++) add(h[cur^1][e[append(j,k)]],h[cur][j]); } cur^=1; } }}int main(int argc,char **argv){// freopen("farben2.txt","w",stdout); sscanf(argv[1],"%d",&m); ma=fp(m+1,m); pw[0]=1; for(int i=1;i<=m;i++) pw[i]=pw[i-1]*(m+1); gao1::gao(); gao2::gao(); for(int i=1;i 