Submission #679742

#	Time	Username	Problem	Language	Result	Execution time	Memory
679742		amir	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	26 ms	37916 KiB

anagramistica

/*
<< 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 + 10 , 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 (ll i = 0 ; i < maxn ; i++) 
		C[i][0] = 1ll ;
	for (ll N = 1 ; N < maxn ;N++){
		for (ll r = 1 ; r < maxn ; r++){
			C[N][r] = C[N-1][r] + C[N-1][r-1] ;
			C[N][r] %= mod ;
		}
	}
	
	cin >> n >> k ;
	for (ll i = 0 ; i < n ; i++){
		string t ;
		cin >> t ;
		sort(all(t)) ;
		cnt[t] ++ ;
	}
	ll ind = 1 ;
	dp[0][0] = 1 ;
	for (pair<string , ll> x : cnt){
		ll Cnt = x.second ;
		//debug(Cnt) ;
		/*if (ind == 1){
			for (ll j = 0 ;j <= Cnt ; j++){
				dp[1][C[j][2]] += C[Cnt][j] ;
				dp[1][C[j][2]] %= mod ;
			}
			ind ++ ;
			continue ;
		}*/
		for (ll i = 0 ; i <= k ; i++){
			for (ll j = 0 ; j <= Cnt ; j++){
				ll idx = i-C[j][2] ;
				if (idx < 0)continue ;
				ll temp = dp[ind-1][idx]*C[Cnt][j] ; temp %= mod ;
				dp[ind][i] += temp ;
				dp[ind][i] %= mod ;
			}
		}
		ind ++ ;
	}
	cout << (dp[ind-1][k]%mod) << '\n' ;
}

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