为什么我也想的是背包？

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+10,P=1e9+7;
int fac[N],facc[N],dp[N][N],n,m,k;map<string,int>mp;vector<int>vec;
bool cmp(int x,int y){return x>y;}
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
int c(int n,int m){if(n<m)return 0;return fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;}
signed main()
{
	cin>>n>>k;
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%P;
	for(int i=1;i<=100;i++)facc[i]=i*(i-1)/2;
	for(int i=1;i<=n;i++)
	{
		string s;cin>>s;
		sort(s.begin(),s.end());
		mp[s]++;
	}
	for(auto i:mp)vec.push_back(i.second);sort(vec.begin(),vec.end(),cmp);
	m=vec.size();dp[0][0]=1;
	for(int i=0;i<m;i++)for(int j=0;j<=k;j++)
	{
		dp[i+1][j]=(dp[i+1][j]+dp[i][j])%P;
		for(int l=1;l<=vec[i]&&facc[l]+j<=k;l++)
			dp[i+1][j+facc[l]]=(dp[i+1][j+facc[l]]+dp[i][j]*c(vec[i],l))%P;
	}
	cout<<dp[m][k]<<'\n';
	return 0;
}

题目链接

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

首先对每个字符串内的字符从小到大排序，相同的就是题目中「相似」的。我们把相同的字符串都归为一组，接下来用 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;
}