Submission #391949

#	Time	Username	Problem	Language	Result	Execution time	Memory
391949		Jarif_Rahman	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	40 ms	50736 KiB

anagramistica

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll md = 1e9 + 7;
struct combination{
    vector<vector<ll>> ncr;
    combination(int k){
        ncr = vector<vector<ll>>(k, vector<ll>(k, 0));
        for(int i = 0; i < k; i++) ncr[i][0] = 1;
        for(int i = 1; i < k; i++) for(int j = 1; j <= i; j++) ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%md;
    }
};
inline ll pw(ll x, ll p){
    if(p == 0) return 1;
    if(p%2 == 0) return((x*x)%md,  p/2);
    return (pw(x, p-1)*x)%md;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<str> v(n);
    for(str &s: v){
        cin >> s;
        sort(s.begin(), s.end());
    }
    sort(v.begin(), v.end());
    vector<int> sth;
    ll ans = 0, p = 0;
    for(int i = 0; i < n; i++){
        if(i != 0 && v[i] == v[i-1]){
            sth.back()++;
        }
        else{
            sth.pb(1);
        }
    }
    n = sth.size();
    combination cmb(2500);
    vector<vector<ll>> dp(n, vector<ll>(k+1, 0));
    for(int i = n-1; i >= 0; i--){
        ll c = sth[i];
        for(int ki = 0; ki <= k; ki++){
            for(int j = 0; j <= c; j++){
                ll x = j;
                x = x*(x-1)/2;
                if(x > ki) continue;
                if(x == ki && i == n-1){
                    dp[i][ki]+=cmb.ncr[c][j];
                    dp[i][ki]%=md;
                    continue;
                }
                if(i == n-1) continue;
                dp[i][ki]+=(cmb.ncr[c][j]*dp[i+1][ki-x])%md;
                dp[i][ki]%=md;
            }
        }
    }
    ans = dp[0][k];
    ans%=md;
    cout << ans << "\n";
}

Compilation message (stderr)

anagramistica.cpp: In function 'll pw(ll, ll)':
anagramistica.cpp:19:30: warning: left operand of comma operator has no effect [-Wunused-value]
   19 |     if(p%2 == 0) return((x*x)%md,  p/2);
      |                         ~~~~~^~~
anagramistica.cpp: In function 'int main()':
anagramistica.cpp:33:17: warning: unused variable 'p' [-Wunused-variable]
   33 |     ll ans = 0, p = 0;
      |                 ^

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