「Luogu 5196」Cow Poetry

Description

题目链接:Luogu 5196

不为 Farmer John 所知的是,Bessie 还热衷于资助艺术创作!最近,她开始研究许多伟大的诗人们,而现在,她想要尝试创作一些属于自己的诗歌了。Bessie 认识 $n$ 个单词,她想要将她们写进她的诗。Bessie 已经计算了她认识的每个单词的长度 $s_i$,以音节为单位,并且她将这些单词划分成了不同的“韵部”,第 $i$ 个单词的韵部为 $c_i$。每个单词仅与属于同一韵部的其他单词押韵。

Bessie 的每首诗由 $m$ 行组成,每一行必须由 $k$ 个音节构成。此外,Bessie 的诗必须遵循某个指定的押韵模式。每行有一个押韵模式,用大写字母 $e_i$ 表示。所有押韵模式等于 $e_i$ 的行必须以同一韵部的单词结尾。不同 $e_i$ 值的行并非必须以不同的韵部的单词结尾。

Bessie 想要知道她可以写出多少首符合限制条件的不同的诗,答案对 $10^9+7$ 取模。

数据范围:$1\le n,k\le 5\times 10^3$,$1\le m\le 10^5$,$1\le s_i\le k$,$1\le c_i\le n$


Solution

很显然是一个 $\text{DP}$ 计数题。定义状态 $f(i,j)$ 表示长度为 $i$ 的句子,以 $j$ 韵部结尾的方案数。

我们枚举当前长度 $i$,以韵部 $j$ 结尾,上一个单词的韵部 $k$,那么有转移:

略作优化后写成伪代码就是:

1
2
3
4
5
6
7
8
for(int i=1;i<=k;++i) {
for(int j=1;j<=n;++j) {
if(i<s[j]) continue;
for(int k=1;k<=n;++k) {
f[i][c[j]]+=f[i-s[j]][k];
}
}
}

很显然这个转移是 $O(n^2k)$ 的,无法接受。

我们发现最外面的 $i$ 和 $j$ 的枚举是没法去掉了,试图把内层的 $k$ 的循环优化掉。设 $g(i)$ 表示长度为 $i$ 的总方案数:

那么我们的转移就是:

最后考虑句子的统计。记韵部为 $i$ 的句子有 $cnt_i$ 个,那么答案就是:

时间复杂度:$O(nk)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>

const int N=5e3+5;
const int mod=1e9+7;
int n,m,k,l[N],c[N],f[N][N],g[N],cnt[26];

void upd(int &x,int y) {
(x+=y)>=mod&&(x-=mod);
}
char getc() {
char c=getchar();
while(c<'A'||c>'Z') c=getchar();
return c;
}
int pow(int x,int p) {
int ans=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ans=1LL*ans*x%mod;
return ans;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i) scanf("%d%d",&l[i],&c[i]);
g[0]=1;
for(int i=1;i<=k;++i) {
for(int j=1;j<=n;++j) if(i>=l[j]) upd(f[i][c[j]],g[i-l[j]]);
for(int j=1;j<=n;++j) upd(g[i],f[i][j]);
}
for(int i=1;i<=m;++i) ++cnt[getc()-'A'];
int ans=1;
for(int i=0;i<26;++i) if(cnt[i]) {
int sum=0;
for(int j=1;j<=n;++j) upd(sum,pow(f[k][j],cnt[i]));
ans=1LL*ans*sum%mod;
}
printf("%d\n",ans);
return 0;
}
0%