Submission #391946

#	Time	Username	Problem	Language	Result	Execution time	Memory
391946		Jarif_Rahman	Anagramistica (COCI21_anagramistica)	C++17	0 / 110	282 ms	50728 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;
const int lim = 20001;
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);
    vector<ll> nn(lim);
    vector<vector<pair<ll, ll>>> s(lim);
    for(int i = 0; i < lim; i++) nn[i] = (ll)i*(i-1)/2;
    for(int i = 0; i < lim; i++) for(int j = 0; j < lim; j++) if(nn[i]+nn[j] < lim) s[nn[i]+nn[j]].pb({i, j});
    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+2, 0));
    for(int i = n-1; i >= 0; i--){
        ll c = sth[i];
        for(int ki = 0; ki <= k; ki++){
            for(auto [a, b]: s[ki]){
                if(a > c) continue;
                if(a != 0) a++;
                if(b != 0) b++;
                ll x = a*(a-1)/2, y = b*(b-1)/2;
                if(x == ki && i == n-1 && b == 0){
                    dp[i][ki]+=cmb.ncr[c][a];
                    dp[i][ki]%=md;
                    continue;
                }
                //if(ki == 0 && i == 1) cout << a << " " << b << " " << cmb.ncr[c][a]*dp[2][y] << "d\n";
                if(i == n-1) continue;
                dp[i][ki]+=(cmb.ncr[c][a]*dp[i+1][y])%md;
                dp[i][ki]%=md;
            }
        }
    }
    ans = dp[0][k+1];
    ans%=md;
    cout << ans << "\n";
}

Compilation message (stderr)

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

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