http://www.lydsy.com/JudgeOnline/problem.php?id=1879

?

f[i][j] 表示匹配了i個字符，匹配字符串的狀態為j的方案數

枚舉下一個字符是什么

計算加上這個自字符之后新匹配到的狀態s

f[i+1][s]+=f[i][j]

?

轉移的時候判斷如果f[i][j]==0，就不用枚舉字符了

沒有這個復雜度在6e8，TLE

其實可以預處理 g[i][j]表示已經匹配了長度為i，再加字符j 可以匹配到的狀態

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;const int N=1<<15; const int mod=1000003;char s[16][51];int f[51][N];int bit[16];int count(int x) {int sum=0;while(x) {sum+=x&1;x>>=1;}return sum; }int main() {bit[0]=1;for(int i=1;i<=15;++i) bit[i]=bit[i-1]<<1;int T;scanf("%d",&T);int n,t,m,len;int S,nj;int ans;while(T--){scanf("%d%d",&n,&t);memset(f,0,sizeof(f));m=0;for(int i=1;i<=n;++i) {scanf("%s",s[i]+1);len=strlen(s[i]+1);m=max(m,len);}S=bit[n];for(int i=0;i<26;++i){nj=0;for(int j=1;j<=n;++j)if(s[j][1]==i+'a' || s[j][1]=='?') nj+=bit[j-1];f[1][nj]++;}for(int i=1;i<m;++i)for(int j=0;j<S;++j)if(f[i][j])for(int k=0;k<26;++k){nj=0;for(int l=1;l<=n;++l)if(j&bit[l-1])if(s[l][i+1]==k+'a' || s[l][i+1]=='?') nj+=bit[l-1];f[i+1][nj]+=f[i][j];f[i+1][nj]-=f[i+1][nj]>=mod ? mod : 0;}ans=0;for(int i=0;i<S;++i)if(count(i)==t){ans+=f[m][i];ans-=ans>=mod ? mod : 0;}cout<<ans<<'\n';} }

?

1879: [Sdoi2009]Bill的挑戰

Time Limit:?4 Sec??Memory Limit:?64 MB
Submit:?919??Solved:?477
[Submit][Status][Discuss]

Description

Input

本題包含多組數據。? 第一行：一個整數T，表示數據的個數。? 對于每組數據：? 第一行：兩個整數，N和K（含義如題目表述）。? 接下來N行：每行一個字符串。 T ≤ 5，M ≤ 15，字符串長度≤ 50。

Output

如題

Sample Input

5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??

Sample Output

914852
0
0
871234
67018

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/8256761.html

總結

以上是生活随笔為你收集整理的bzoj千题计划207：bzoj1879: [Sdoi2009]Bill的挑战的全部內容，希望文章能夠幫你解決所遇到的問題。

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