前言

這是一道Burnside引理的應用題

題目相關

鏈接

題目大意

一個長度為$n$的$01$圈，沒有超過$k$個的連續的$1$，求方案數

數據范圍

$T\le 50,n\le 2000,k\le 2000$

題解

我們設$f_i$表示不含超過$k$個連續$1$的長度為$i$的鏈的數量
我們考慮求$f_i$，用所有方案減去不合法方案數，對于一個長度為$i?1$的不合法方案，其后面再加上一個數字，其依然不合法，然后我們考慮因為加入最后一位而不合法的串，一定是最后$k+1$位是$1$，倒數第$k+2$位是$0$，并且其它位合法，那么直接遞推即可

我們設$h_i$表示長度為$i$、包含至少一個$0$、不含超過連續$k$個$1$的環的數量(固定$1$號點)
先不說要如何計算

我們考慮答案，我們列出Burnside引理的式子
$$l=\frac{1}{|G|}\sum _{a_i\in G}{c}_1(a_i)$$
我們發現對于所有置換（即所有$0\le i<n$，轉動$i$次），其$c(a_i)$剛好是最小整除周期是$i$的因數的方案數，實際操作的時候我們發現$c(a_i)=h_{gcd(i,n)}$

我們考慮如何求$h_i$，我們發現我們可以在一條鏈的兩端連上$01???10$形式的一串（其中$1$的數量要小于等于$k$），我們枚舉$1$的數量至少為幾，我們再枚舉接入的位置，我們發現，插入的元素越多，方案越多
我們設原串為$X$，插入的$i$個$1$在頭與尾的串分別為$A$和$B$，我們發現，最后一定是“$A0X0B$”的形式，我們發現若$1$的個數為$i$，那么就有$i+1$種方案
那么我們考慮對$f$進行前綴和，并且對于所有$i$直接轉移選$i$~$k$個的方案，那么$i$個的方案就會被轉移到$i+1$次，即可

我們發現只有$i$是$n$的因數時，$h_i$是要求的，直接$dp$一個$h_i$在$i\le k$的時候是$\mathcal{O}(1)$的，$i>k$的時候是$\mathcal{O}(k)$的，那么總復雜度為
$$\mathcal{O}?\sum _{i>k,i|n}k?$$
我們設大于$k$且是$n$的因數的數有$x$個，容易發現$n$的因數從大到小排，第$j$個的值小于等于$\frac{n}{j}$，那么$k\le \frac{n}{x}$，那么$x?k\le n$，即直接$dp$是$\mathcal{O}(n)$的

另外，我們發現對于所有$c(a_i)$的求和可以枚舉j=gcd(i,n)，那么貢獻次數就是$\phi (\frac{n}{i})$，我們可以通過線性篩篩$\phi$，并且枚舉$j$，這樣就可以做到$\mathcal{O}(n)$的復雜度

綜上，總復雜度$\mathcal{O}(n)$

代碼

#include<bits/stdc++.h> typedef long long ll; #define rg register template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;} template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');} template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} const int maxn=2001; const ll mod=100000007; inline int pow(int x,int y) {int res=1;for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;return res; } inline void md(int&x){if(x>=mod)x-=mod;} inline int Md(const int x){return x>=mod?x-mod:x;} int n,k,bit[maxn],F[maxn+5],*f=F+5,h[maxn],sum; ll T,ans; bool isprime[maxn];int prime[maxn],primesize,phi[maxn]; inline void getphi(const int size) {phi[1]=1;memset(isprime,1,sizeof(isprime));for(rg int i=2;i<=size;i++){if(isprime[i])prime[++primesize]=i,phi[i]=i-1;for(rg int j=1;j<=primesize&&(ll)prime[j]*i<=size;j++){isprime[prime[j]*i]=0;if(i%prime[j]==0){phi[prime[j]*i]=phi[i]*prime[j];break;}phi[prime[j]*i]=phi[i]*(prime[j]-1);}} } int main() { // freopen("party.in","r",stdin),freopen("party.out","w",stdout);bit[0]=1;for(rg int i=1;i<=2000;i++)bit[i]=Md(bit[i-1]<<1);getphi(2000);read(T);while(T--){read(n),read(k);if(k>n)k=n;sum=0,ans=0;memset(F,0,sizeof(F));memset(h,0,sizeof(h));for(rg int i=0;i<=k;i++)f[i]=bit[i];f[-1]=1;for(rg int i=k+1;i<=n;i++){sum=Md(Md(sum<<1)+f[i-k-2]);f[i]=Md(bit[i]-sum+mod);}for(rg int i=0;i<=n;i++)f[i]=Md(f[i]+f[i-1]);for(rg int i=1;i<=n;i++)if(n%i==0){if(i<=k)h[i]=bit[i]-1;else for(rg int j=0;j<=k;j++)h[i]=Md(Md(h[i]+f[i-j-2])+mod-f[i-k-3]);ans+=(ll)h[i]*phi[n/i]%mod;}print(((ans%mod+mod)*pow(n,mod-2)+(n==k))%mod),putchar('\n');}return 0; }

總結

Burnside引理知道就好
主要是要求的東西會求
優化復雜度大法好

總結

以上是生活随笔為你收集整理的[bzoj1547]周末晚会的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。