oj.uz

Submission #475225

# Submission time Handle Problem Language Result Execution time Memory
475225 2021-09-21T14:39:15 Z keta_tsimakuridze Anagramistica (COCI21_anagramistica) C++14
110 / 110
 124 ms 6612 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,k,dp[N],fact[N],invfact[N];
map<string,int> cnt;
string s[N];
int C(int a,int b) {
	if(a < b) return 0;
	return fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}
int pwr(int u,int v) {
	int ans = 1;
	while(v) {
		if(v%2) ans = ans * u % mod;
		v /= 2;
		u = u * u % mod;
	}
	return ans;
}
main(){
	cin >> n >> k;
	fact[0] = invfact[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> s[i];
		sort(s[i].begin(),s[i].end());
		cnt[s[i]]++;
		fact[i] = fact[i - 1] * i % mod;
		invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
	}
	dp[0] = 1;
	for(int i = 1; i <= n; i++) {
	
		for(int j = k; j >= 0; j--) {
			for(int p = 1; p <= cnt[s[i]]; p++) {
				if(p * (p - 1) / 2 <= j)dp[j] = (dp[j] + dp[j - p * (p - 1)/2] * C(cnt[s[i]],p)) % mod;
		}}

		cnt[s[i]] = 0;
	}
	cout << dp[k];
 }

Compilation message

anagramistica.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6580 KB Output is correct
2 Correct 4 ms 6464 KB Output is correct
3 Correct 4 ms 6476 KB Output is correct
4 Correct 5 ms 6556 KB Output is correct
5 Correct 4 ms 6560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6572 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 7 ms 6588 KB Output is correct
4 Correct 8 ms 6604 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6580 KB Output is correct
2 Correct 4 ms 6464 KB Output is correct
3 Correct 4 ms 6476 KB Output is correct
4 Correct 5 ms 6556 KB Output is correct
5 Correct 4 ms 6560 KB Output is correct
6 Correct 5 ms 6572 KB Output is correct
7 Correct 6 ms 6604 KB Output is correct
8 Correct 7 ms 6588 KB Output is correct
9 Correct 8 ms 6604 KB Output is correct
10 Correct 26 ms 6560 KB Output is correct
11 Correct 14 ms 6604 KB Output is correct
12 Correct 7 ms 6612 KB Output is correct
13 Correct 17 ms 6608 KB Output is correct
14 Correct 22 ms 6604 KB Output is correct
15 Correct 17 ms 6520 KB Output is correct
16 Correct 81 ms 6604 KB Output is correct
17 Correct 124 ms 6612 KB Output is correct
18 Correct 7 ms 6580 KB Output is correct