/*
<< in the name of Allah >>
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end()
#define sz(x) (int)x.size()
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' ;
const ll maxn = 2e3 + 3 , mod = 1e9 + 7 ;
ll dp[maxn][maxn] ;
ll n , k ;
ll C[maxn][maxn] ;
map<string , ll> cnt ;
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(NULL) ;
cout.tie(NULL) ;
/*for (int r = 0 ; r < maxn ; r++)
C[0][r] = 0 ;*/
for (int i = 0 ; i < maxn ; i++)
C[i][0] = 1 ;
for (int N = 1 ; N < maxn ;N++){
for (int r = 1 ; r < maxn ; r++)
C[N][r] = C[N-1][r] + C[N-1][r-1] ;
}
cin >> n >> k ;
for (int i = 0 ; i < n ; i++){
string t ;
cin >> t ;
sort(all(t)) ;
cnt[t] ++ ;
}
int ind = 1 ;
for (pair<string , int> x : cnt){
ll Cnt = x.second ;
if (ind == 1){
for (int j = 0 ;j <= Cnt ; j++){
dp[1][C[j][2]] = C[Cnt][j] ;
}
ind ++ ;
continue ;
}
//debug(Cnt) ;
for (int i = 0 ; i <= k ; i++){
for (int j = 0 ; j <= Cnt ; j++){
int idx = i-C[j][2] ;
if (idx < 0)continue ;
ll temp = dp[ind-1][idx]*C[Cnt][j] ; temp %= mod ;
dp[ind][i] += temp ;
}
}
ind ++ ;
}
cout << dp[ind-1][k] << '\n' ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
31828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
