P2167 [SDOI2009]Bill的挑战
发布时间:2020-12-14 04:18:38 所属栏目:大数据 来源:网络整理
导读:sb状压dp。 设f[i][j]表示字符串前i位和集合为j的串匹配的方案数。 枚举哪个字母直接转移就好了。 (话说为啥这种水题都有紫色难度 #includebits/stdc++.h#define il inline#define vd void#define mod 1000003typedef long long ll;il int gi(){ int x=0,f=
sb状压dp。 设f[i][j]表示字符串前i位和集合为j的串匹配的方案数。 枚举哪个字母直接转移就好了。 (话说为啥这种水题都有紫色难度 #include<bits/stdc++.h> #define il inline #define vd void #define mod 1000003 typedef long long ll; il int gi(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } char _S[20][54]; ll f[52][1<<15]; int S[20][54],yes[53][27]; int cnt[1<<15]; int main(){ #ifndef ONLINE_JUDGE freopen("2167.in","r",stdin); freopen("2167.out","w",stdout); #endif int T=gi(),n,k,len,U; for(int i=1;i<1<<15;++i)cnt[i]=cnt[i-(i&-i)]+1; while(T--){ n=gi(),k=gi();U=(1<<n)-1; memset(yes,sizeof yes); for(int i=1;i<=n;++i){ scanf("%s",_S[i]+1); if(i==1)len=strlen(_S[i]+1); for(int j=1;j<=len;++j){ if(_S[i][j]=='?')S[i][j]=0; else S[i][j]=_S[i][j]-'a'+1; yes[j][S[i][j]]|=1<<i-1; } } memset(f,sizeof f); f[0][U]=1; for(int i=0;i<len;++i) for(int j=0;j<1<<n;++j) if(f[i][j]){ f[i][j]%=mod; for(int k=1;k<27;++k)f[i+1][j&(yes[i+1][k]|yes[i+1][0])]+=f[i][j]; } ll ans=0; for(int i=0;i<1<<n;++i)if(cnt[i]==k)ans+=f[len][i]%mod; printf("%lldn",ans%mod); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |