oj.uz

Submission #679865

# Submission time Handle Problem Language Result Execution time Memory
679865 2023-01-09T13:17:34 Z ajab_01 Anagramistica (COCI21_anagramistica) C++17
110 / 110
 10 ms 6356 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 2e3 + 3;
const int MOD = 1e9 + 7;
long long dp[N][N] , fac[N] , rev[N];
vector<string> vec;
vector<int> v;
int n , k , cnt = 1;
string s[N];

long long power(int a , int b){
	if(!b) return 1ll;
	long long tmp = power(a , b / 2);
	tmp = tmp * tmp % MOD;
	if(b & 1) tmp = tmp * a % MOD;
	return tmp;
}

void cal(){
	fac[0] = 1;
	for(int i = 1 ; i < N ; i++)
		fac[i] = fac[i - 1] * i % MOD;
	rev[N - 1] = power(fac[N - 1] , MOD - 2);
	for(int i = N - 2 ; i >= 0 ; i--)
		rev[i] = rev[i + 1] * (i + 1) % MOD;
}

long long C(int n , int r){
	if(r > n) return 0ll;
	return fac[n] * rev[r] % MOD * rev[n - r] % MOD;
}

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

	cal();

	cin >> n >> k;
	for(int i = 0 ; i < n ; i++){
		cin >> s[i];
		sort(s[i].begin() , s[i].end());
		vec.push_back(s[i]);
	}

	sort(vec.begin() , vec.end());

	v.push_back(-1);

	for(int i = 1 ; i < n ; i++){
		if(vec[i] != vec[i - 1]){
			v.push_back(cnt);
			cnt = 0;
		}
		cnt++;
	}

	v.push_back(cnt);

	int sz = (int)v.size();

	for(int i = 0 ; i <= v[1] ; i++){
		if(!i){
			dp[1][0]++;
			continue;
		}

		if(i == 1){
			dp[1][0] += v[1];
			continue;
		}

		if(C(i , 2) > k) break;

		dp[1][C(i , 2)] = (dp[1][C(i , 2)] + C(v[1] , i)) % MOD;
	}

	for(int i = 2 ; i < sz ; i++){
		for(int j = 0 ; j <= k ; j++){
			for(int num = 0 ; num <= v[i] ; num++){
				if(C(num , 2) > j) break;
				dp[i][j] = (dp[i][j] + C(v[i] , num) * dp[i - 1][j - C(num , 2)] % MOD) % MOD;
			}
		}
	}

	// for(int i = 1 ; i < sz ; i++)
	// 	for(int j = 0 ; j <= k ; j++)
	// 		cout << i << '&' << j << ": " << dp[i][j] << '\n';

	cout << dp[sz - 1][k] << '\n';

	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 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 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 724 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1748 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 0 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 1748 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 1748 KB Output is correct
10 Correct 3 ms 2048 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 10 ms 6356 KB Output is correct
17 Correct 8 ms 852 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct