Submission #447905

#	Time	Username	Problem	Language	Result	Execution time	Memory
447905		Jasiekstrz	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	30 ms	37704 KiB

anagramistica

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e3;
const int MOD=1e9+7;
map<string,int> cnt;
int t[N+10];
long long ch[N+10][N+10];
long long dp[N+10][N+10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		sort(s.begin(),s.end());
		cnt[s]++;
	}
	ch[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		ch[i][0]=1;
		for(int j=1;j<=n;j++)
			ch[i][j]=(ch[i-1][j-1]+ch[i-1][j])%MOD;
	}
	n=0;
	for(auto &v:cnt)
		t[++n]=v.se;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			for(int l=0;l<=t[i] && ch[l][2]<=j;l++)
				dp[i][j]=(dp[i][j]+dp[i-1][j-ch[l][2]]*ch[t[i]][l])%MOD;
		}
	}
	cout<<dp[n][k]<<"\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70