Submission #679969

#TimeUsernameProblemLanguageResultExecution timeMemory
679969Shadii_usfAnagramistica (COCI21_anagramistica)C++14
10 / 110
5 ms1748 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e3 + 10, mod = 1e9 + 7; long long dp[maxn][maxn] , f[maxn] , invf[maxn] , anss; long long power(int a , int b){ if(b == 0){ return 1; } anss = power(a , b/2); anss *= anss; anss %= mod; if(b & 1){ anss *= a; anss %= mod; } return anss; } long long c(int n , int k){ if(k > n){ return 0; } return f[n] * invf[k] % mod * invf[n - k] % mod; } int main(){ int n , k , cnt = 1 , sizee; string a[maxn]; bool mark[maxn] , markk[maxn]; vector <int> v; cin >> n >> k; for(int i=1 ; i<=n ; i++){ cin >> a[i]; } for(int i=1 ; i<=n ; i++){ sizee = a[i].size(); for(int j = 0 ; j<sizee ; j++){ mark[a[i][j] - 'a'] = true; } if(!markk[i]){ for(int j = 1 ; j<=n ; j++){ bool x = true; if(!markk[j] && j != i){ int sizee = a[j].size(); for(int m = 0 ; m<sizee ; m++){ if(!mark[a[j][m] - 'a']){ x = false; break; } } if(x){ cnt++; markk[j] = true; } } } v.push_back(cnt); markk[i] = true; } sizee = a[i].size(); for(int j = 0 ; j<sizee ; j++){ mark[a[i][j] - 'a'] = false; } cnt = 1; } f[0] = invf[0] = 1; for(int i=1 ; i<maxn ; i++){ f[i] = f[i-1] * i; f[i] %= mod; invf[i] = power(f[i] , mod - 2); } for(int i=0 ; i<=v[0] ; i++){ int num = c(i , 2); dp[0][num] += c(v[0] , i); } sizee = v.size(); for(int i=1 ; i<sizee ; i++){ for(int j=0 ; j<=k ; j++){ int m = 0; while(c(m , 2) <= j && m <= v[i]){ dp[i][j] = dp[i][j] + (dp[i - 1][j - c(m , 2)] * c(v[i] , m) % mod) % mod; dp[i][j] %= mod; m++; } } } sizee = v.size(); cout << dp[sizee - 1][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...