自动搬运

查看原文

来自洛谷，原作者为

	Henry_he **

搬运于2025-08-24 22:08:07，当前版本为作者最后更新于2019-03-06 21:37:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单的计数题

有题意得知，每一行都只关心最后一个词的韵部

所以前面的词可以随便乱填（好诗~）

规定$f\left[ j \right]$表示音节填了$j$ 位的方案总数

for(int j=0;j<=k;j++)
	for(int i=1;i<=n;i++)
		f[j+s[i]]+=f[j];

(直接复制可能会有一些小问题~)

然后再统计最后一个词的韵部的方案数

只要枚举单词给它空个位置就好啦

g[c[i]]+=f[k-s[i]]

然后就可以啦~

最后把每个韵部要求统计的行数都就求出来就好了

丑陋的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 5005
using namespace std;
typedef long long LL;
int n,m,k;
LL s[N],c[N];
LL f[N],g[N];
LL nd[30];
const LL mod=1000000007;
LL ksm(LL b,LL k)
{
	if(k==0) return 1;
	if(k==1) return b%mod;
	LL q=ksm(b,k>>1);
	if(k&1) return q*q%mod*b%mod;
	else return q*q%mod;
}
bool cmp(LL x,LL y)
{
	return x>y;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&s[i],&c[i]);
	f[0]=1;
	for(int j=0;j<=k;j++)
	if(f[j]) 
		for(int i=1;i<=n;i++)
			if(j+s[i]<=k)	f[j+s[i]]=(f[j+s[i]]+f[j])%mod;
	for(int i=1;i<=n;i++)
		g[c[i]]=(g[c[i]]+f[k-s[i]])%mod;
	while(m--)
	{
		char s[5];
		scanf("%s",s);
		nd[s[0]-'A']++;
	}
	sort(nd,nd+26,cmp);
	sort(g+1,g+n+1,cmp);
	LL ans=1;
	for(int i=0;i<26&&nd[i];i++)
	{
		LL x=nd[i],sum=0;
		for(int j=1;j<=n&&g[j];j++)
			sum=(sum+ksm(g[j],x))%mod;
		ans=ans*sum%mod; 	
	}
	printf("%lld\n",ans);
	return 0;
}