【2020.12.02提高组模拟】球员(player)
题目
题目描述
老师们已经知道学生喜欢睡觉,Soaring是这项记录保持者。他只会在吃饭或玩FIFA20时才会醒来。因此,他经常做关于足球的梦,在他最近的一次梦中,他发现自己成了皇家马德里足球俱乐部的总经理。
他的工作是挑选N名球员争取在下个赛季打败巴塞罗那队,但是董事会有两个特殊的要求。具体如下:
①所有运动员姓氏的长度必须不同。
②每个运动员的姓氏必须是长度比其长的所有其他运动员姓氏的连续子串
为了让工作变得简单,Soaring将潜在的球员分成N类,第i类的球员的姓氏恰好有i个字母,且每一类恰好有K个球员。
Soaring想知道有多少种不同的方法选出满足要求的N个球员。答案对(10^9^+7)取余。
题解
题目大意:有\(n\)种不同长度的字符串,每种字符串有\(k\)个,第\(i\)中字符串的长度是\(i\),现在要从\(n\)种字符串里每种选一个,使得选出的字符串都是所有长度比其长的字符串的连续字串,问有多少种选择方案,对\(10^9+7\)取模
22%
暴力从每种里选择,再暴力判断是否合法
时间复杂度\(O(k^nn^4)\),预计得分22
100%
首先我们知道,若\(a\)是\(b\)的连续字串,\(b\)是\(c\)的连续子串,那么\(a\)一定是\(c\)的连续字串
那么判断时就可以只判断\(i\)和\(i+1\)的关系,而\(i\)与\(i+1\)的长度只相差1,说明想要是连续子串,要么是末尾空一个字母,要么开头空一个字母
考虑\(dp\),设\(f[i][j]\)表示到了第\(i\)种,第\(i\)种选择第\(j\)个的方案数,那么枚举\(u\),若\(u\)是\(j\)的子串,那么转移:\(f[i][j]+=f[i-1][u]\)
答案是\(\sum_{i=1}^kf[n][i]\)
Code
#include<cstdio>
#define ll long long
#define mod 1000000007
#define N 55
#define K 1505
using namespace std;
int n,m;
ll sq,sh,ans,a[N][K][N],f[N][K];
char s[N];
ll mi(int x)
{
ll res=1;
for (int i=1;i<=x;++i)
res=res*26%mod;
return res;
}
int main()
{
freopen("player.in","r",stdin);
freopen("player.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
{
for (int j=1;j<=m;++j)
{
scanf("%s",s+1);
for (int k=1;k<=i;++k)
a[i][j][k]=(a[i][j][k-1]*26%mod+s[k]-'a')%mod;
}
}
for (int i=1;i<=m;++i)
f[1][i]=1;
for (int i=2;i<=n;++i)
for (int j=1;j<=m;++j)
{
sq=a[i][j][i-1];//当前字符串的1~i-1位
sh=(a[i][j][i]-mi(i-1)*a[i][j][1]%mod+mod)%mod;//当前字符串的2~i位
for (int k=1;k<=m;++k)
if (a[i-1][k][i-1]==sq||a[i-1][k][i-1]==sh/*判断是否是连续子串*/) f[i][j]=(f[i][j]+f[i-1][k])%mod;
}
for (int i=1;i<=m;++i)
ans=(ans+f[n][i])%mod;
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- Linux_10个需要了解的Linux网络和监控命令(转)
- tail -f 和 -F 的用法
- Currency System in Geraldion
- file_get_contents模仿浏览器头(user_agent)获取数据
- js控制html文字提示语的出现和隐藏
- WPF中利用后台代码实现窗口分栏动态改变
- 【POJ2155】【二维树状数组】Matrix
- Java NIO 学习笔记五 缓冲区补充
- kafka的安装以及基本用法
- DHCP工作原理简析
- Python爬虫之使用celery加速爬虫
- 30、进程的基础理论,并发(multiprocessing模块)
- 「Python」6种python中执行shell命令方法
- 第二十单元 计划任务crond服务
- 2018.4.23 git命令总结
- 通用Mapper
- Android性能测试--垃圾回收频次统计的作用
- (一)SpringMVC
- Linux 安装配置 Nginx
- 【pyhon】nvshens图片批量下载爬虫