自动搬运

查看原文

来自洛谷，原作者为

	MinimumSpanningTree **

搬运于2025-08-24 22:30:56，当前版本为作者最后更新于2024-10-22 20:49:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接

看完题解感觉这题的状态表示和转移方程好像还挺好想到的，不知道为什么自己考场上会想成一种奇怪的背包。

首先对每个字符串内的字符从小到大排序，相同的就是题目中「相似」的。我们把相同的字符串都归为一组，接下来用 map 就可以统计出每一组的字符串有多少个。这里用 $cnt_i$ 表示第 $i$ 组的字符串个数。接下来我们就可以从字符串组数和题目中的 $k$ 下手。

• 状态表示：$dp_{i,j}$ 表示考虑前 $i$ 组字符串，恰好 $j$ 对相似字符串的方案数。

• 状态转移：

  • 初始化：$dp_{0,0}=1$，唯一的方案是不取任何东西。

  • $dp_{i,j}+=dp_{i-1,j}$，因为前 $i$ 组包含了前 $i-1$ 组，并且后面的枚举没有计算到第 $i$ 组取 $0$ 个字符串的情况。

  • 枚举第 $i$ 组字符串选择的字符串个数 $o$，$o$ 个相同的字符串一共能产生 $\frac{o(o-1)}{2}$ 的贡献，而要从第 $i$ 组中取出 $o$ 个，有 $C^o_{cnt_i}$ 种情况，所以 $dp_{i,j}+=\sum_{o=1}^{j}dp_{i-1,j-\frac{o(o-1)}{2}}\times C^o_{cnt_i}$。

• 答案在哪：$dp_{n,k}$，其中 $n$ 表示的是字符串组数，$k$ 为题目中的含义。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=2e3+100;
int n,k,cnt[N],id;
ll dp[N][N],c[N][N];
string s;
unordered_map<string,int> um;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		sort(s.begin(),s.end()); 
		//map将「相似」的字符串归一组 
		if(um.count(s)) cnt[um[s]]++;
		else um[s]=++id,cnt[id]=1;
	}
	for(int i=0;i<=n;i++)//杨辉三角预处理出组合数 
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
	}
	dp[0][0]=1;//初始化 
	for(int i=1;i<=id;i++)//考虑前i组 
	{
		for(int j=0;j<=k;j++)//恰好j对相似 
		{
			dp[i][j]=dp[i-1][j];
			//枚举第i组取的字符串个数o 
			for(int o=1;o<=cnt[i]&&o*(o-1)/2<=j;o++) dp[i][j]=(dp[i][j]+dp[i-1][j-o*(o-1)/2]*c[cnt[i]][o]%MOD)%MOD;
		}
	}
	printf("%lld",dp[id][k]);
	return 0;
}