oj.uz

Submission #715119

# Submission time Handle Problem Language Result Execution time Memory
715119 2023-03-25T22:59:44 Z TheConverseEngineer Anagramistica (COCI21_anagramistica) C++17
10 / 110
 2 ms 1620 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;
int 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] = (int)(dp[n][k] + (((choose((ll)pools[n-1], (ll)i)%MOD)*dp[n-1][k-(i*(i-1))/2])%MOD)%MOD);
			}
		}
	}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 2 ms 1620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Incorrect 2 ms 1620 KB Output isn't correct
8 Halted 0 ms 0 KB -