Submission #392123

#	Time	Username	Problem	Language	Result	Execution time	Memory
392123		soroush	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	52 ms	460 KiB

anagramistica

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2020;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , k;

map < string , int > cnt;
int dp[maxn] , pd[maxn];
ll fact[maxn] , inv[maxn];

int C(int r , int n){
	if(r > n)return(0);
	return((fact[n] * inv[r])%mod * inv[n - r])%mod;
}

int32_t main(){
	migmig;
	cin >> n >> k;
	fact[0] = inv[0] = 1;
	for(int i = 1 ; i < maxn ; i ++)
		fact[i] = (fact[i - 1] * i)%mod , inv[i] = pw(fact[i] , mod - 2);
	for(int i = 1 ; i <= n ; i ++){
		string s;
		cin >> s;
		sort(s.begin() , s.end());
		cnt[s]++;
	}
	dp[0] = 1;
	for(auto u : cnt){
		int v = u.second;
		for(int i = 0 ; i < maxn ; i ++)pd[i] = dp[i];
		for(int i = 1 ; i <= v ; i ++){
			int c = C(2, i);
			for(int j = c ; j < maxn ; j ++){
				pd[j] = (pd[j] + (dp[j - c] * 1LL * C(i , v))%mod)%mod;
			}
		}
		for(int i = 0 ; i < maxn ; i ++)dp[i] = pd[i];
	}
	cout << dp[k];
	return(0);
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70