Submission #715120

#	Time	Username	Problem	Language	Result	Execution time	Memory
715120		TheConverseEngineer	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	7 ms	6372 KiB

anagramistica

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70