Submission #679766

#	Time	Username	Problem	Language	Result	Execution time	Memory
679766		Iliya	Anagramistica (COCI21_anagramistica)	C++17	10 / 110	1 ms	468 KiB

anagramistica

//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;
}

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