「Luogu 5196」Cow Poetry

发表于 | | 阅读次数:
字数统计: 825 字

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%