洛谷 P7552 [COCI2020-2021#6] Anagramistica 题解
题目链接
看完题解感觉这题的状态表示和转移方程好像还挺好想到的，不知道为什么自己考场上会想成一种奇怪的背包。
首先对每个字符串内的字符从小到大排序，相同的就是题目中「相似」的。我们把相同的字符串都归为一组，接下来用 map 就可以统计出每一组的字符串有多少个。这里用
-
状态表示：
dp_{i,j} 表示考虑前i 组字符串，恰好j 对相似字符串的方案数。 -
状态转移：
-
初始化：
dp_{0,0}=1 ，唯一的方案是不取任何东西。 -
-
枚举第
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;
}