列表

详情


NC229895. 牛牛写作文

描述

牛牛想要写一篇文章,他已经在脑中构造好了 n 个句子。

但是因为句子实在是太多了!他并不想要自己筛选,于是他想要随机选一些句子构成一片文章。

所以牛牛每次会随机等概率地进行一下操作:

1. 停笔。即结束这篇作文。
2. 写下第 1 个句子。
3. 写下第 2 个句子。
4.
5. 写下第 n 个句子。
也就是说,写下任意一个句子和停笔的概率都是

写完作文后牛牛突然想起一个重要的句子必须写进作文里,但是作文已经写完了,牛牛只能祈祷在文章中找的到这个句子。

请你帮牛牛求出重要句子出现至少一次的概率,并对 取模。

输入描述

第一行一个整数 n

2 行到 行每行一个字符串。第 i 行的表示第 i-1 个句子。

行一个字符串 s。表示重要的句子。

对于所有数据点,满足,所有字符串长度 ,且仅由小写字母组成。

输出描述

一个整数表示重要句子至少只出现一次的概率对  取模的结果。

示例1

输入:

1
a
aa

输出:

250000002

说明:

在第一步有1\over 2停止写作,否则写下一个a

同样在第二步有1\over2的概率停止写作,否则再次写下一个a

所以写出aa的概率就是1\over{2} \times1\over 2=1\over4

示例2

输入:

3
ab
ba
a
aa

输出:

444444448

说明:

样例答案为 \dfrac{4}{9}

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

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];
}

上一题