oj.uz

Submission #858086

# Submission time Handle Problem Language Result Execution time Memory
858086 2023-10-07T11:55:27 Z serifefedartar Anagramistica (COCI21_anagramistica) C++17
110 / 110
 5 ms 712 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 500 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 3 ms 712 KB Output is correct
17 Correct 5 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct