oj.uz

Submission #679771

# Submission time Handle Problem Language Result Execution time Memory
679771 2023-01-09T07:31:38 Z Iliya Anagramistica (COCI21_anagramistica) C++17
110 / 110
 11 ms 6252 KB 
//Ye Rooz Khoob Miad ???
#include<bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size
 
using namespace std;
typedef long long ll;
 
const int N = 2e3 + 10;
const int Inf = 1'061'109'567;
const int Mod = 1e9 + 7; 

int power(int a, int b) {
	if(b == 0) 
		return 1;
	int res = power(a, b / 2);
	res = 1LL * res * res % Mod;
	if(b & 1)
		res = 1LL * res * a % Mod;
	return res;
}

int fac[N + 10], revfac[N + 10];

int C(int n, int r) {
	return 1LL * fac[n] * revfac[r] % Mod * revfac[n - r] % Mod;
}

void pre() {
	fac[0] = 1;
	for(int i = 1; i < N; i++) 
		fac[i] = 1LL * fac[i - 1] * i % Mod;
	revfac[N - 1] = power(fac[N - 1], Mod - 2);
	for(int i = N - 2; i >= 0; i--) 
		revfac[i] = 1LL * (i + 1) * revfac[i + 1] % Mod;
}

ll n, k, dp[N][N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	pre();

	cin >> n >> k;
	map<string, int> MP;
	for(int i = 0; i < n; i++) {
		string str;
		cin >> str;
		sort(all(str));
		MP[str]++;
	}
	int i = 0;
	dp[0][0] = 1;
	for(auto x : MP) { i++;
		for(int j = 0; j <= k; j++) {
			for(int l = 0; l <= x.S; l++) {
				if(j < C(l, 2)) continue;
				dp[i][j] = (dp[i][j] + (dp[i - 1][j - C(l, 2)] * C(x.S, l)) % Mod) % Mod;
			}
		}
	}
	cout << dp[i][k];
 
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 468 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 1 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 468 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 4 ms 2004 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 3 ms 1236 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 10 ms 6252 KB Output is correct
17 Correct 11 ms 724 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct