Submission #716125

#	Time	Username	Problem	Language	Result	Execution time	Memory
716125		Iliya_	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	26 ms	37660 KiB

anagramistica

// IN THE NAME OF GOD
#include<bits/stdc++.h>
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define flush cout.flush();
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;

const ll N = 2e3 + 2, mod = 1e9+7, mod0 = 1e9+7, base0 = 73, mod1 = 998244353, base1 = 89; 
vector<pair<ll,ll>> having; 
vector<ll> cnt; 
string s; 
ll dp[N][N], c[N][N]; 

ll power(ll a, ll b){
	if (b == 0) return 1;
	ll c = power(a,b/2); 
	return c*c%mod * (b&1 ? a : 1) % mod; 
}

void hashing(){
	sort(s.begin(),s.end()); 
	ll ans0 = 0, ans1 = 0;
	for(char c : s){
		ans0 = ans0 * base0 % mod0 + (c-'a'+1); ans0 %= mod0;
		ans1 = ans1 * base1 % mod1 + (c-'a'+1); ans1 %= mod1; 
	}
	having.push_back({ans0,ans1}); 
}

void cmaking(){
	c[0][0] = 1; 
	for(int i=1; i<N; i++) for(int j=0; j<N; j++) c[i][j] = (j == 0 ? 1 : c[i-1][j] + c[i-1][j-1]), c[i][j] %= mod;
}

void solve(){  
	cmaking(); 
	int n,k; cin >> n >> k;
	for(int i=0; i<n; i++) cin >> s, hashing();
	sort(having.begin(),having.end()); 
	cnt.push_back(1); 
	for(int i=1; i<int(having.size()); i++){
		if (having[i].first == having[i-1].first && having[i].second == having[i-1].second) cnt.back()++; 
		else cnt.push_back(1); 
	}
	dp[0][0] = 1;
	for(int i=1; i<=int(cnt.size()); i++){
		for(int j=0; j<=k; j++){
			for(int taking = 0; taking <= cnt[i-1]; taking++){
				if (c[taking][2] > j) break; 
				dp[i][j] = dp[i][j] + dp[i-1][j-c[taking][2]] * c[cnt[i-1]][taking] % mod; dp[i][j] %= mod;
			}
		}
	}
	cout << dp[int(cnt.size())][k] << endl; 
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; t=1; //cin >> t;
	while(t--){solve();}
}

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