LG5196 「USACO2019JAN」Cow Poetry 背包+乘法原理

\(\mathrm{Cow Poetry}\)

问题描述

LG5196

题解

因为每句诗的长度一定是\(k\)，所以自然而然想到背包。

设\(opt[i][j]\)代表到第\(i\)位时，结尾为\(j\)的方案数。

背包，注意\(\mathrm{DP}\)顺序为先枚举\(i\)，后枚举单词。（Debug了一小时就因为这个）

然后乘法原理统计答案即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

void fr(int &x){

	char ch=1;

	while(!(ch>='A'&&ch<='Z')) ch=getchar();

	x=ch-'A'+1;

}

const int mod=1000000007;

const int maxn=5003;

const int maxm=100100;

int n,m,k;

int s[maxn],c[maxn];

int e[maxn];

int opt[maxn][maxn],sum[maxm];

void Init(){

	read(n);read(m);read(k);

	for(int i=1;i<=n;i++){

		read(s[i]);read(c[i]);

	}

	for(int i=1;i<=m;i++){

		fr(e[i]);

	}

}

void dp(){

	sum[0]=1;

	for(int i=1;i<=k;i++){

		for(int j=1;j<=n;j++){

			if(i<s[j]) continue;

			opt[i][c[j]]=(opt[i][c[j]]+sum[i-s[j]])%mod;

			sum[i]=(sum[i]+sum[i-s[j]])%mod;

		}

	}

}

int tot,cnt[27];

int ksm(long long x,int p){

	long long ret=1;

	while(p){

		if(p&1) ret=ret*x%mod;p>>=1;

		x=x*x%mod;

	}

	return ret;

}

void Work(){

	dp();

	long long ans=0,sum=1;

	for(int i=1;i<=m;i++) ++cnt[e[i]];

	for(int i=1;i<=26;i++){

		if(!cnt[i]) continue;

		ans=0;

		for(int j=1;j<=n;j++){

			if(!opt[k][j]) continue;

			ans=(ans+ksm(opt[k][j],cnt[i]))%mod;

		}

		sum=sum*ans%mod;

	}

	printf("%lld\n",sum);

}

int main(){

	freopen("poetry.in","r",stdin);freopen("poetry.out","w",stdout);

	Init();Work();

	fclose(stdin);fclose(stdout);

	return 0;

}