列表

详情

NC205303. 古老的打字机

描述

Compute 在他的家里找到了一个打字机，他想要用这个打字机来打字，但是这个打字机实在是太古老了，以至于它根本就无法打出正确的内容。
给定 n 个由小写字母组成的字符串 ，每个字符串有一个价值 v_i。
现在 Compute 会用这个打字机来打字，他会敲击打字机 m 次，得到字符串 t。其中，每次敲击会等概率地输入一个小写字母或者退格（Backspace）。
退格的作用是把当前得到的字符串的最后一个字符删除。特别地，如果当前字符串是空串，退格后仍为空串。
定义他最后所得到的字符串的价值为：每个串 s_i 在得到的串 t 中的出现次数 c_i 与 价值 v_i 的乘积。即
其中 表示 t 串从第 i 个字符到 第 j 个字符组成的子串；
艾佛森括号。
Compute 想要知道他得到的字符串价值的期望是多少。
可以证明这个期望的 倍是一个整数，因此你只需要求出它的 倍对 取模后的结果。

输入描述

第一行包含两个整数 n, m ()， 中间以空格分隔，分别表示字符串的个数和 Compute 的敲击次数。
接下来 n 行，每行包含一个由小写字母组成的字符串 s_i ()和一个整数 v_i ()，中间以空格分隔，分别表示给定的字符串和它的价值。
输入保证 。

输出描述

在一行输出一个整数，表示 Compute 打出的随机字符串价值的期望的  倍对  取模后的结果。

示例1

输入: 

1 1
a 1

输出: 

1

示例2

输入: 

2 2
a 1
aa 2

输出: 

55

示例3

输入: 

3 3
a 1
aa 2
aaa 3

输出: 

2242

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 16ms, 内存消耗: 4456K, 提交时间: 2020-04-18 14:38:10 

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define fr first
#define sc second
using namespace std;
typedef long long ll;
const int N=1e3+10;
const int inf=1e9;
const int mo=1e9+7;
char s[N];int a[N][N],ny[N];
ll qk(ll x,int y){ll r=1;
	for(;y;y>>=1){
		if(y&1)r=r*x%mo;x=x*x%mo;
	}return r;
}
int main(){int n,m,ans=0;
	scanf("%d%d",&n,&m);
	ny[0]=1;ny[1]=qk(26,mo-2);
	rep(i,2,m)ny[i]=1ll*ny[i-1]*ny[1]%mo;
	a[0][0]=1;
	rep(i,0,m-1){
		rep(j,0,i){
			a[i+1][j+1]=(a[i+1][j+1]+26ll*a[i][j])%mo;
			(a[i+1][j?j-1:0]+=a[i][j])%=mo;
		}
	}
	rep(i,1,n){int v;
		scanf("%s%d",s,&v);
		int l=strlen(s);
		rep(j,l,m){
			ans=(ans+(ll)a[m][j]*ny[l]%mo*v%mo*(j-l+1))%mo;
		}
	}
	printf("%d\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 194ms, 内存消耗: 4456K, 提交时间: 2020-04-18 16:45:48 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010,mo=1e9+7;

long long Pow(long long x,int p)
{
	long long res=1;
	while (p)
	{
		if (p&1) (res*=x)%=mo;
		(x*=x)%=mo;
		p>>=1;
	}
	return res;
}

int f[maxn][maxn];
char s[maxn];
int v[maxn];
int n,m,ans;

int main()
{
	scanf("%d%d",&n,&m);
	f[0][0]=1;
	for (int i=1;i<=m;i++)
	{
		f[i][0]=(f[i-1][1]+f[i-1][0])%mo;
		for (int j=1;j<=m;j++) f[i][j]=(f[i-1][j-1]*26ll+f[i-1][j+1])%mo;
	}
	for (int i=1;i<=n;i++)
	{
		int len,v;
		scanf("%s%d",s,&v);
		len=strlen(s);
		for (int j=len;j<=m;j++)
			ans=(ans+f[m][j]*Pow(Pow(26,len),mo-2)%mo*(j-len+1)%mo*v%mo)%mo;
	}
	printf("%d\n",ans);
}

上一题

© 2025 nowcoder.com