NC24213. [USACO 2019 Jan G]Cow Poetry
描述
Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。
Bessie想要知道她可以写出多少首符合限制条件的不同的诗。
输入描述
输入的第一行包含N、M和K。
以下N行，每行包含两个整数si（1≤si≤K）和ci（1≤ci≤N）。这表示Bessie认识一个长度（以音节为单位）为si、属于韵部ci的单词。
最后M行描述了Bessie想要的押韵模式，每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。
输出描述
输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。
示例1
输入:
3 3 10 3 1 4 1 3 2 A B A
输出:
960
说明:
在这个例子中，Bessie认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗（其中1，2、3分别代表第一个、第二个、第三个单词）：121 123 321。C++11(clang++ 3.9) 解法, 执行用时: 438ms, 内存消耗: 528K, 提交时间: 2019-11-26 16:59:25
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e3+5;
ll mod=1e9+7;
ll n,m,k;
ll f[N];
ll ty[N];
ll cnt[50];
ll ans[50],sum;
struct words{
ll len,c;
}w[N];
ll qpow(ll x,ll y)
{
ll tot=1;
while(y){
if(y&1)tot=(tot*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return tot;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(ll i=1;i<=n;i++)scanf("%d%d",&w[i].len,&w[i].c);
char c;
for(ll i=1;i<=m;i++)
{
c=getchar();
c=getchar();
cnt[c-'A'+1]++;
}
f[0]=1;
for(ll i=0;i<=k;i++)
for(ll j=1;j<=n;j++)
if(i+w[j].len<=k)
{
f[i+w[j].len]=(f[i+w[j].len]+f[i])%mod;
}
for(ll i=1;i<=n;i++)ty[w[i].c]=(ty[w[i].c]+f[k-w[i].len])%mod;
ans[0]=1;
for(ll i=1;i<=26;i++)
{
ans[i]=ans[i-1];
if(!cnt[i])continue;
sum=0;
for(ll j=1;j<=n;j++)sum=(sum+qpow(ty[j],cnt[i]))%mod;
ans[i]=ans[i]*sum%mod;
}
cout<<ans[26];
}
C++14(g++5.4) 解法, 执行用时: 79ms, 内存消耗: 668K, 提交时间: 2020-08-31 12:34:35
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m,k,s[5005],c[5005],t[30];
int dp[5005],g[5005],ans[30];
char e;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y/=2;
}
return res;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d %d",&s[i],&c[i]);
dp[0]=1;
for(int j=0;j<=k;j++)
for(int i=1;i<=n;i++)
if(j+s[i]<=k) dp[j+s[i]]+=dp[j],dp[j+s[i]]%=mod;
for(int i=1;i<=n;i++){
g[c[i]]+=dp[k-s[i]];
g[c[i]]%=mod;
}
for(int i=1;i<=m;i++) scanf("%s",&e),t[e-'A'+1]++;
ans[0]=1;
for(int i=1;i<=26;i++){
if(t[i]==0){ans[i]=ans[i-1];continue;}
int f=0;
for(int j=1;j<=n;j++) f+=ksm(g[j],t[i]),f%=mod;
ans[i]=1ll*ans[i-1]*f%mod;
}
printf("%d\n",ans[26]);
return 0;
}