hdu_6021 MG loves string

题目:

  MG is a busy boy. And today he's burying himself in such a problem:
  For a length of , a random string made of lowercase letters, every time when it transforms, all the character i will turn into .
  MG states that the consists of a permutation .
  Now MG wants to know the expected steps the random string transforms to its own.
  It's obvious that the expected steps will be a decimal number.
  You should output .

思路:

  如果单个字母考虑是否被取到,那么复杂度最少也是,过得了就有鬼了。。。。
  考虑到长度一样的置换对答案的影响时一样的,所以可以根据长度把这些置换分类,再分每一类考虑取和不取。因为,所以最多只有类,那么这里的复杂度就是了。
  接下来的问题就是把个物体分到个集合,要求每个集合至少有一个的方案数。方案数乘以所有置换长度的LCM就是当前情况的贡献了。
  一开始的想法是考组合数算出有多少重复的,发现比较难算,后来想了一个比较好实现的做法。
  用二进制保存集合中有无元素,记录数组代表重复计算的次数,每次计算完当前情况后更新所有包含当前集合的集合的值即可。那么每次的方案数就是为可取的元素个数。枚举包含当前集合的集合可以通过一个循环实现:for(int fa=bin;fa<MAX;fa=(fa+1)|bin)

代码:

#include <bits/stdc++.h>
#define ll long long
#define clr(a) memset(a,0,sizeof(a))
#define MOD 1000000007
ll pow(ll a,int k){
    ll ans=1;
    while(k){
        if(k&1)ans=ans*a%MOD;
        a=(a*a)%MOD;
        k>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
char s[30];
int n,Cnt[30],tot,p[10],bok[(1<<8)+5];
bool vis[30];
void init(){
    clr(vis);clr(Cnt);tot=0;
    for(int i=1;i<=26;i++)
        if(!vis[i]){
            int x=s[i]-'a'+1,cnt=1;
            while(x!=i){
                vis[x]=true;
                x=s[x]-'a'+1;
                cnt++;
            }
            Cnt[cnt]+=cnt;
        }
    for(int i=1;i<=26;i++)
        if(Cnt[i])
            p[tot++]=i;
}
int main(){
    int T;
    ll ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d%s",&n,s+1);
        init();ans=0;
        clr(bok);
        for(int bin=1;bin<(1<<tot);bin++){
            ll cnt=0,LCM=1,tmp=0;
            for(int i=0;i<tot;i++)
                if(bin>>i&1){
                    tmp+=Cnt[p[i]];
                    LCM=lcm(LCM,p[i]);
                }
            cnt=((pow(tmp,n)-bok[bin])%MOD+MOD)%MOD;
            (ans+=cnt*LCM)%=MOD;
            for(int x=bin;x<(1<<tot);x=(x+1)|bin)
                (bok[x]+=cnt)%=MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}