oj.uz

Submission #858083

# Submission time Handle Problem Language Result Execution time Memory
858083 2023-10-07T11:53:02 Z serifefedartar Anagramistica (COCI21_anagramistica) C++17
10 / 110
 1 ms 348 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 = 998244353;
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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -