P5196 [USACO19JAN] Cow Poetry G

luogu题目传送门

题目背景

USACO19 年一月金组第一题

题目描述

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

Bessie 的每首诗由 $M$ 行组成（$1\le M\le 10^5$），每一行必须由 $K$（$1\le K\le 5000$）个音节构成。此外，Bessie 的诗必须遵循某个指定的押韵模式。

Bessie 想要知道她可以写出多少首符合限制条件的不同的诗。

输入格式

输入的第一行包含 $N$、$M$ 和 $K$。

以下 $N$ 行，每行包含两个整数 $s_i$（$1\le s_i\le K$）和 $c_i$（$1\le c_i\le N$）。这表示 Bessie 认识一个长度（以音节为单位）为 $s_i$、属于韵部 $c_i$ 的单词。

最后 $M$ 行描述了 Bessie 想要的押韵模式，每行包含一个大写字母 $e_i$。所有押韵模式等于 $e_i$ 的行必须以同一韵部的单词结尾。不同 $e_i$ 值的行并非必须以不同的韵部的单词结尾。

输出格式

输出 Bessie 可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对 $1,000,000,007$ 取余的结果。

输入输出样例 #1

输入 #1

3 3 10
3 1
4 1
3 2
A
B
A

输出 #1

960

说明/提示

在这个例子中，Bessie 认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有 $960$ 首这样的诗。以下是一首满足要求的诗（其中 $1,2,3$ 分别代表第一个、第二个、第三个单词）：$\text{121 123 321}$。

思路

由于它要写很多行诗，我们先考虑每一个韵脚怎么办？

令a[u]表示以 i 为韵脚的一行诗有多少种方案

如果字母 c 出现了num[c]次，那么这几行诗的方案数为$ans[c]={\sum }_{i=1}^{n}a[i{]}^{num[c]}$，因为一行诗我们可以写很多次。

那对于不同韵脚，如果韵脚有重复的怎么办？

仔细读题，你会发现"所有押韵模式等于 $e_i$ 的行必须以同一韵部的单词结尾。不同 $e_i$ 值的行并非必须以不同的韵部的单词结尾。"所以我们根本不需要管重不重复，那最后的方案书即为${\prod }_{cϵ韵脚}ans[c]$

那给我们的问题只有一个了：如何求出a数组？

我们有$O(n^2)$的时间复杂度可以让我们完成这一步。定义dp[i][j]表示已经写道了第 i 个位置，以韵脚 j 结尾的方案数，那么$dp[i][j]={\sum }_{p=1}^{n}dp[i-s[j]][c[p]]$。但是这个方案根据分析，时间复杂度为$O(n^{2}k)$，我们无法接受。我们发现${\sum }_{p=1}^{n}dp[i-s[j]][c[p]]$是一定的，那我们每次在dp[i][j]更新后，我们用一个sum数组将其加到sum[i]中，这样就可以了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e3+5,mod=1000000007;
ll n,m,k,dp[N][N],sum[N],a[N],s[N],c[N],q[N],o;
ll vis[N],num[N];
ll qpow(ll a,ll b){//快速幂
	ll ret=1;
	while(b){
		if(b%2==1)ret=ret*a%mod;
		a=a*a%mod;
		b=b/2;
	}
	return ret;
}
int main(){
	cin>>n>>m>>k;
	for(ll i=1;i<=n;i++)cin>>s[i]>>c[i];
	for(ll i=1;i<=n;i++)dp[s[i]][i]=1;
	for(ll i=1;i<=k;i++){
		for(ll j=1;j<=n;j++){
			if(i-s[j]<0)continue;
			dp[i][j]=(dp[i][j]+sum[i-s[j]])%mod;
			sum[i]=(sum[i]+dp[i][j])%mod;
		}
	}//求出dp数组 
	for(ll i=1;i<=N-5;i++)a[c[i]]=(a[c[i]]+dp[k][i])%mod;//求出a数组
	char x;
	for(int i=1;i<=m;i++){
		cin>>x;
		int y=int(x);
		if(!vis[y]){vis[y]=1;q[++o]=y;}//q数组记录字母
		num[y]++;
	}
	ll ans=1;
	for(int i=1;i<=o;i++){
		ll js=0;
		for(int j=1;j<=5000;j++)js=(js+qpow(a[j],num[q[i]]))%mod;
		ans=(ans%mod*js)%mod;//求出答案 
	}
	cout<<ans<<'\n';
	return 0;
}