Submission #679732

#	Time	Username	Problem	Language	Result	Execution time	Memory
679732		parsadox2	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	12 ms	14316 KiB

anagramistica

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e3 + 10 , mod = 1e9 + 7;

int n , k , dp[maxn] , cnt[maxn] , val[maxn] , C[maxn][maxn];
string ar[maxn];

int32_t main()
{
	fast;
	
	C[0][0] = 1;
	for(int i = 1 ; i < maxn ; i++)
	{
		C[i][0] = 1;
		for(int j = 1 ; j <= i ; j++)
		{
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++)
	{
		cin >> ar[i];
		sort(ar[i].begin() , ar[i].end());
	}
	sort(ar , ar + n);
	int ps = 1;
	cnt[ps] = 1;
	for(int i = 1 ; i < n ; i++)
	{
		if(ar[i] != ar[i - 1])
			ps++;
		cnt[ps]++;
	}
	dp[0] = 1;
	for(int i = 1 ; i <= ps ; i++)
	{
		for(int j = k ; j > -1 ; j--)
		{
			for(int num = 1 ; num <= cnt[i] ; num++)
			{
				if(j < C[num][2])
					break;
				dp[j] = (dp[j] + 1LL * C[cnt[i]][num] * dp[j - C[num][2]] % mod) % mod;
			}
		}
	}
	cout << dp[k] << endl;
	return 0;
}

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