題目鏈接：點擊查看

題目大意：給出一個匹配串 $s$，現在問模式串 $t$ 的期望得分。其中假設匹配串在模式串中的出現次數為 $x$，那么將得到 $2^x$ 的分數

題目分析：涉及到了期望一開始還以為是概率，后來發現其實就是個計數問題

題目實際讓我們操作的就是，枚舉 $5^n$ 種字符串，然后對于每種字符串統計匹配串 $s$ 的出現次數，注意這里的出現次數并不能說是最多或最少的出現次數，先將貢獻的式子轉換一下：
$2^x=(...((1)?2)?2)?2...)?2$

假設枚舉的字符串 $t$ 中可以匹配一次 $s$ ，那么只需要將匹配次數相應的乘以二就可以實現上面的公式了，關于期望的話最后只需要除以 $5^n$ 就好啦

現在問題轉換為了字符串計數問題，我的第一反應就是 $AC$ 自動機裸題啊，直接掛上模板過了，簡單講一下思路，就是將匹配串扔進 $AC$ 自動機里，$d{p}_{i,j}$ 代表到了字符串 $t$ 的第 $i$ 個位置時，在自動機里匹配的狀態為 $j$ 的方案數，轉移的話就是枚舉第 $i+1$ 的字符記為 $ch$，方程就是：
$d{p}_{i+1,trie[j][ch]}+=dp[i][j]$

非常簡單的過了，不過后續意識到是不是有點大材小用了？因為這個題目只有一個匹配串啊，為什么不直接用 $KMP$ 去寫呢？然后就用 $KMP$ 也寫了一發。。不過有一說一，對于失配狀態轉移的 $dp$，以后還是用自動機來寫吧，因為相比之下 $KMP$ 的細節略多

代碼：
AC自動機

// Problem: Connie // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17148/D // Memory Limit: 1048576 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=110; const int mod=998244353; const char str[]="conie"; char s[N]; LL dp[N][N]; int fail[N],flag[N],trie[N][26],cnt; int newnode() {cnt++;for(int i=0;i<26;i++) {trie[cnt][i]=0;}flag[cnt]=false;return cnt; } void insert_word() {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=newnode();pos=trie[pos][to];}flag[pos]=true; } void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} } LL q_pow(LL a,LL b) {LL ans=1;while(b) {if(b&1) {ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);scanf("%s",s);insert_word();getfail();dp[0][0]=1;for(int i=0;i<n;i++) {for(int j=0;j<=cnt;j++) {for(int k=0;k<5;k++) {int nj=trie[j][str[k]-'a'];dp[i+1][nj]=(dp[i+1][nj]+dp[i][j]*(flag[nj]?2:1))%mod;}}}LL ans=0;for(int i=0;i<=cnt;i++) {ans=(ans+dp[n][i])%mod;}ans=(ans*q_pow(q_pow(5,n),mod-2))%mod;cout<<ans<<endl;return 0; }

KMP：

// Problem: Connie // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17148/D // Memory Limit: 1048576 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=998244353; const char str[]="conie"; char s[N]; int nt[N]; void get_next() {int len=strlen(s+1);nt[1]=0;for(int i=2,j=0;i<=len;i++) {while(j!=0&&s[j+1]!=s[i]) {j=nt[j];}if(s[j+1]==s[i]) {j++;}nt[i]=j;} } LL dp[110][110]; LL q_pow(LL a,LL b) {LL ans=1;while(b) {if(b&1) {ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);scanf("%s",s+1);get_next();dp[0][0]=1;for(int i=0;i<n;i++) {for(int j=0;j<=m;j++) {for(int k=0;k<5;k++) {char ch=str[k];int p=j;while(p!=0&&ch!=s[p+1]) {p=nt[p];}if(ch==s[p+1]) {p++;}dp[i+1][p]=(dp[i+1][p]+dp[i][j]*(p==m?2:1))%mod;}}}LL ans=0;for(int i=0;i<=m;i++) {ans=(ans+dp[n][i])%mod;}ans=(ans*q_pow(q_pow(5,n),mod-2))%mod;cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的牛客 - Connie(AC自动机+dp/KMP+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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