Submission #858086

#	Time	Username	Problem	Language	Result	Execution time	Memory
858086		serifefedartar	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	5 ms	712 KiB

anagramistica

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 2100;

map<vector<int>, int> mp;
ll dp[MAXN], fact[MAXN], inv[MAXN];

ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

ll calc(ll x) {
	return (x * (x - 1) / 2) % MOD;
}

ll nCr(ll n, ll r) {
	return (fact[n] * inv[r] % MOD) * inv[n-r] % MOD;
}

int main() {
	fast
	fact[0] = inv[0] = 1;
	for (ll i = 1; i < MAXN; i++) {
		fact[i] = (fact[i-1] * i) % MOD;
		inv[i] = expo(fact[i], MOD - 2); 
	}

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		vector<int> cnt(26, 0);
		for (auto u : s)
			cnt[u-'a']++;
		mp[cnt]++;
	}

	vector<int> cnt;
	for (auto u : mp)
		cnt.push_back(u.s);

	dp[0] = 1;
	for (auto u : cnt) {
		for (int j = k; j >= 0; j--) {
			for (int q = u; q >= 1; q--) {
				if (j + calc(q) <= k)
					dp[j+calc(q)] = (dp[j+calc(q)] + nCr(u, q) * dp[j]) % MOD;
			}
		}
	}
	cout << dp[k] << "\n";
}

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