This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e3+5, MOD = 1e9+7;
int fact[N];
int fastpow(int n, int p){
int res = 1;
while(p){
if(p&1) res = res * n % MOD;
n = n * n % MOD;
p >>= 1;
}
return res;
}
void init(){
fact[0] = 1;
for(int i = 1;i < N;i++)
fact[i] = fact[i-1] * i % MOD;
}
int nCr(int n, int r){
if(n < r) return 0;
return fact[n]*fastpow(fact[r],MOD-2)%MOD*fastpow(fact[n-r],MOD-2)%MOD;
}
signed main(){
fastio
init();
int n,k;
cin >> n >> k;
map<string,int> m;
for(int i = 0;i < n;i++){
string s;
cin >> s;
sort(s.begin(),s.end());
m[s]++;
}
vector<int> v;
v.push_back(0);
for(auto [a,b] : m){
v.push_back(b);
}
n = v.size();
int dp[n][k+1] = {};
dp[0][0] = 1;
for(int a = 1;a < n;a++){
for(int j = k;~j;j--){
dp[a][j] = dp[a-1][j];
}
int x = v[a];
for(int i = 1;i <= x;i++){
int tmp = i*(i-1)/2;
for(int j = k;~j;j--){
if(j < tmp) break;
dp[a][j] = (dp[a][j] + dp[a-1][j-tmp]*nCr(x,i)) % MOD; \
}
}
}
cout << dp[n-1][k] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |