oj.uz

Submission #403175

# Submission time Handle Problem Language Result Execution time Memory
403175 2021-05-12T21:53:28 Z MohamedAhmed04 Anagramistica (COCI21_anagramistica) C++14
110 / 110
 16 ms 16332 KB 
#include <bits/stdc++.h>

using namespace std ;

const int mod = 1e9 + 7 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Sub(int x , int y)
{
	int z = x - y ;
	if(z < 0)
		z += mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (x * 1ll * y) % mod ;
}

int powlog(int base , int power)
{
	if(power == 0)
		return 1 ;
	int x = powlog(base , power / 2) ;
	x = Mul(x , x) ;
	if(power & 1)
		x = Mul(x , base) ;
	return x ;
}

int modinv(int x)
{
	return powlog(x , mod-2) ;
}

int Div(int x , int y)
{
	return Mul(x , modinv(y)) ;
}

struct combination
{
    vector<int>fact , inv ;
    combination(int sz) : fact(sz + 1) , inv(sz + 1)
    {
        fact[0] = 1 ;
        inv[0] = 1 ;
        for(int i = 1 ; i <= sz ; ++i)
            fact[i] = Mul(fact[i-1] , i) ;
        inv[sz] = modinv(fact[sz]) ;
		for(int i = sz-1 ; i >= 1 ; --i)
		    inv[i] = Mul(inv[i+1] , i+1) ;
    }
    int choose(int n , int k) const
    {
        if(k < 0 || n < k)
            return 0 ;
        return Mul(Mul(fact[n] , inv[k]) , inv[n - k]) ;
    }
};

const int MAX = 2000 + 10 ;

combination comb(MAX) ;

string arr[MAX] ;
int n , k ;

map<string , int>mp ;
vector<int>v ;

int dp[MAX][MAX] ;

int solve(int idx , int rem)
{
	if(idx == n)
		return (rem == 0) ;
	int &ret = dp[idx][rem] ;
	if(ret != -1)
		return ret ;
	ret = solve(idx+1 , rem) ;
	int sum = 0 ; 
	for(int i = 0 ; i < v[idx] ; ++i)
	{
		sum += i ;
		if(sum > rem)
			break ;
		ret = Add(ret , Mul(solve(idx+1 , rem - sum) , comb.choose(v[idx] , i+1))) ;
	}
	return ret ;
}

int main()
{
	memset(dp , -1 , sizeof(dp)) ;
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n ; ++i)
	{
		sort(arr[i].begin() , arr[i].end()) ;
		mp[arr[i]]++ ;
	}
	for(auto &i : mp)
		v.push_back(i.second) ;
	n = v.size() ;
	return cout<<solve(0 , k)<<"\n" , 0 ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16300 KB Output is correct
2 Correct 9 ms 16204 KB Output is correct
3 Correct 9 ms 16076 KB Output is correct
4 Correct 9 ms 16204 KB Output is correct
5 Correct 9 ms 16204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16220 KB Output is correct
2 Correct 9 ms 16204 KB Output is correct
3 Correct 9 ms 16204 KB Output is correct
4 Correct 10 ms 16220 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16300 KB Output is correct
2 Correct 9 ms 16204 KB Output is correct
3 Correct 9 ms 16076 KB Output is correct
4 Correct 9 ms 16204 KB Output is correct
5 Correct 9 ms 16204 KB Output is correct
6 Correct 9 ms 16220 KB Output is correct
7 Correct 9 ms 16204 KB Output is correct
8 Correct 9 ms 16204 KB Output is correct
9 Correct 10 ms 16220 KB Output is correct
10 Correct 11 ms 16204 KB Output is correct
11 Correct 9 ms 16172 KB Output is correct
12 Correct 9 ms 16216 KB Output is correct
13 Correct 9 ms 16268 KB Output is correct
14 Correct 12 ms 16220 KB Output is correct
15 Correct 10 ms 16180 KB Output is correct
16 Correct 16 ms 16332 KB Output is correct
17 Correct 15 ms 16220 KB Output is correct
18 Correct 9 ms 16220 KB Output is correct