제출 #679865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679865		ajab_01	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	10 ms	6356 KiB

anagramistica

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