oj.uz

Submission #715120

# Submission time Handle Problem Language Result Execution time Memory
715120 2023-03-25T23:02:41 Z TheConverseEngineer Anagramistica (COCI21_anagramistica) C++17
110 / 110
 7 ms 6372 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define MOD 1000000007

// combo stuff
ll factorial[2005], inv[2005];
ll pow(ll x, ll y) {
	ll res = 1; x %= MOD;
	while (y) {
		if (y & 1) {
			res = (x*res)%MOD; 
		}
		x = (x*x)%MOD; 
		y >>= 1;
	}
	return res;
}
ll choose(ll n, ll r) {
	if (r == 0) return 1;
	return factorial[n] * inv[r] % MOD * inv[n - r] % MOD;
}

map<string, int> buckets;
ll dp[2005][2005];
int N, K;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> K;
	FOR(i, 0, N) {
		string s; cin >> s; sort(all(s));
		buckets[s]++;
	}
	dp[0][0] = 1; // One way to pick nothing

	// set up combo
	factorial[0] = 1;
	FOR(i, 1, 2005) factorial[i] = (factorial[i-1] * i) % MOD;
	inv[2004] = pow(factorial[2004], (ll)MOD - 2);
	for (int i = 2004; i > 0; i--) inv[i-1] = (inv[i] * i) % MOD;
	
	// dp time
	vi pools(sz(buckets)); int __i = 0;
	for (auto it = buckets.begin(); it != buckets.end(); ++it) pools[__i++] = it->second;
	
	FOR(n, 1, sz(pools)+1) {
		FOR(k, 0, K+1) {
			dp[n][k] = 0;
			for (int i = 0; i <= pools[n-1]; i++) {
				if (k-(i*(i-1))/2 < 0) break; // Can't take this many
				dp[n][k] = (dp[n][k] + (((choose((ll)pools[n-1], (ll)i)%MOD)*dp[n-1][k-(i*(i-1))/2])%MOD)%MOD)%MOD;
			}
		}
	}

	cout << dp[sz(pools)][K];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 1244 KB Output is correct
15 Correct 1 ms 476 KB Output is correct
16 Correct 7 ms 6372 KB Output is correct
17 Correct 6 ms 736 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct