NC229895. 牛牛写作文
描述
输入描述
第一行一个整数 。
第 行到 行每行一个字符串。第 行的表示第 个句子。第 行一个字符串 。表示重要的句子。对于所有数据点,满足,所有字符串长度 ,且仅由小写字母组成。
输出描述
一个整数表示重要句子至少只出现一次的概率对 取模的结果。
示例1
输入:
1 a aa
输出:
250000002
说明:
在第一步有停止写作,否则写下一个a示例2
输入:
3 ab ba a aa
输出:
444444448
说明:
C++(g++ 7.5.0) 解法, 执行用时: 65ms, 内存消耗: 1088K, 提交时间: 2023-03-20 19:58:45
#include<bits/stdc++.h> using namespace std; using ll = long long; constexpr ll P = 1e9 + 7; const int maxn = 210; int nxt[maxn][26], fail[maxn]; ll f[maxn][2*maxn]; ll qpow(ll a, ll k){ ll ans = 1; while(k){ if(k&1) ans = ans * a % P; a = a * a % P, k >>= 1; } return ans; } void solve(){ int m; cin >> m; vector<string>vec(m); for(int i = 0 ; i < m ; i ++) cin >> vec[i]; string s; cin >> s; s = " " + s; int n = s.size()-1; nxt[0][s[1]-'a'] = 1; for(int i = 1 ; i < n ; i ++){ for(int j = 0 ; j < 26 ; j ++){ if(s[i+1]-'a' == j){ nxt[i][j] = i + 1; fail[i+1] = nxt[fail[i]][j]; } else{ nxt[i][j] = nxt[fail[i]][j]; } } } ll inv = qpow(m, P-2); f[n][n] = 1; for(int i = 0 ; i < n ; i ++){ for(auto &tmp: vec){ int now = i; for(auto &ch: tmp){ now = nxt[now][ch-'a']; if(now==n) break; } f[i][now] = (f[i][now] + inv) % P; } } ll p = qpow(m+1, P-2); for(int i = 0 ; i <= n ; i ++){ for(int j = 0 ; j <= n ; j ++){ f[i][j] = (p-1+P) * f[i][j] % P; } f[i][i] = (f[i][i] + 1) % P; f[i][i+n+1] = 1; } for(int i = 0 ; i <= n ; i ++){ for(int j = i ; j <= n ; j ++){ if(f[j][i]){ swap(f[i], f[j]); break; } } assert(f[i][i] != 0); ll inv = qpow(f[i][i], P-2); for(int j = i ; j <= 2*n+1 ; j ++){ f[i][j] = f[i][j] * inv % P; } for(int j = 0 ; j <= n ; j ++){ if(j==i) continue; ll frac = f[j][i]; for(int k = i ; k <= 2*n+1 ; k ++){ f[j][k] = (f[j][k] - f[i][k] * frac) % P; } } } cout << (f[0][2*n+1]+P)*p % P << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
C++ 解法, 执行用时: 76ms, 内存消耗: 800K, 提交时间: 2021-12-10 22:37:21
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define M 1000000007 int i,j,k,n,m,t,len,nxt[1005]; ll f[205][205],inv; ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;} ll su(ll a,ll b){a+=b;return (a>=M)?a-M:a;} string s[1005]; char sb[1005]; int main(){ cin>>n;for(i=1;i<=n;i++)cin>>s[i]; cin>>sb+1;m=strlen(sb+1); for(i=2;i<=m;i++){ while(j&&sb[j+1]!=sb[i]){j=nxt[j];} if(sb[j+1]==sb[i]){j++;}nxt[i]=j; } f[m][m]=f[m][m+1]=1; int it;inv=ksm(n+1,M-2); for(i=0;i<m;i++){ for(j=1;j<=n;j++){ it=i; for(auto k:s[j]){ while(it&&k!=sb[it+1]){it=nxt[it];} if(sb[it+1]==k){it++;}if(it==m){break;} } f[i][it]=su(f[i][it],inv); } f[i][i]=su(f[i][i],M-1); } for(i=0;i<=m;i++){ for(j=i;j<=m;j++)if(f[j][i]){swap(f[i],f[j]);break;} inv=ksm(f[i][i],M-2); for(j=0;j<=m+1;j++)f[i][j]=f[i][j]*inv%M; for(j=0;j<=m;j++){ if(i==j){continue;}inv=f[j][i]; for(k=0;k<=m+1;k++)f[j][k]=su(f[j][k],M-f[i][k]*inv%M); } } cout<<f[0][m+1]; }