代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef pair<int,int> PR;
const int mod=10007,L1=1058400;
const int pri[4]={2,3,5,7},kpri[11]={11,13,17,19,23,29,31,37,41,43,47};
int n,kans[32],tmp[32],mo[12][1060000],cnt[32],vis[12];
vector<int> ans;vector<string> patterns;

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
int re=1;
for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
return re;
}
void extension(int x,int y,int len) {
vis[y]=1;int ll=patterns[x].length();int kjs=0;
for(RI i=0;i<len;++i) if(patterns[x][i%ll]=='M') ++mo[y][i];
}
int getid(int x) {for(RI i=0;i<11;++i) if(kpri[i]==x) return i;}
class CowsMooing{
public:
vector<int> getDistribution(vector<string> kpat) {
patterns=kpat,n=patterns.size();
for(RI i=0;i<n;++i) {
int kl=patterns[i].length();
for(RI j=0;j<4;++j) while(kl%pri[j]==0) kl/=pri[j];
if(kl==1) extension(i,11,L1);
else extension(i,getid(kl),12*kl);
}
for(RI i=0;i<=n;++i) ans.push_back(0);
int lcm=6107;//((50!)*12) mod 10007
for(RI i=0;i<11;++i) if(vis[i]) lcm=1LL*lcm*ksm(kpri[i],mod-2)%mod;
if(vis[11]) lcm=1LL*lcm*ksm(88200,mod-2)%mod;
for(RI i=0;i<12;++i) {
kans[0]=1;for(RI j=1;j<=n;++j) kans[j]=0;
for(RI j=0;j<12;++j) {
if(!vis[j]) continue;
for(RI k=0;k<=n;++k) tmp[k]=kans[k],kans[k]=0;
for(RI k=0;k<=n;++k) cnt[k]=0;
for(RI k=i;k<(j==11?L1:12*kpri[j]);k+=12) ++cnt[mo[j][k]];
for(RI k=0;k<=n;++k)
for(RI t=k;t<=n;++t)
kans[t]=qm(kans[t]+1LL*tmp[t-k]*cnt[k]%mod);
}
for(RI k=0;k<=n;++k) ans[k]=qm(ans[k]+kans[k]);
}
for(RI i=0;i<=n;++i) ans[i]=1LL*ans[i]*lcm%mod;
return ans;
}
};