oj.uz

Submission #709964

# Submission time Handle Problem Language Result Execution time Memory
709964 2023-03-15T02:00:12 Z pcc Trener (COCI20_trener) C++14
110 / 110
 213 ms 6456 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mxn = 51;
const ll mxk = 1505;
const ll mod = 1e9+7;
pll p = {29,37};
pair<pll,pll> vals[mxn][mxk];
pll h[mxn][mxk];
ll dp[mxn][mxk];
ll n,k;
ll pw(ll a,ll b){
    ll re = 1;
    while(b){
        if(b&1)re = re*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return re;
}
ll inv(ll kk){
    return pw(kk,mod-2);
}
ll mad(ll a,ll b){
    a += b;
    if(a>=mod)a -= mod;
    return a;
}

bool eq(pll &a,pll &b){
    return a.fs == b.fs&&a.sc == b.sc;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<k;j++){
            pll tmp = {0,0};
            pll coef = {1,1};
            string s;
            cin>>s;
            for(auto &i:s){
                tmp.fs = mad(tmp.fs,coef.fs*(i-'a'+1)%mod);
                tmp.sc = mad(tmp.sc,coef.sc*(i-'a'+1)%mod);
                coef.fs = coef.fs*p.fs%mod;
                coef.sc = coef.sc*p.sc%mod;
            }
            h[i][j] = tmp;
            auto t1 = tmp;
            t1.fs = mad(t1.fs,mod-(s[0]-'a'+1))*inv(p.fs)%mod;
            t1.sc = mad(t1.sc,mod-(s[0]-'a'+1))*inv(p.sc)%mod;
            vals[i][j].fs = t1;
            tmp.fs = (tmp.fs+mod-pw(p.fs,i)*(s.back()-'a'+1)%mod)%mod;
            tmp.sc = (tmp.sc+mod-pw(p.sc,i)*(s.back()-'a'+1)%mod)%mod;
            vals[i][j].sc = tmp;
        }
    }
    for(int i = 0;i<n-1;i++){
        if(i == 0)for(int j = 0;j<k;j++)dp[i][j] = 1;
        for(int j = 0;j<k;j++){
            for(int kk = 0;kk<k;kk++){
                if(eq(h[i][j],vals[i+1][kk].fs)||eq(h[i][j],vals[i+1][kk].sc))dp[i+1][kk] = mad(dp[i+1][kk],dp[i][j]);
            }
        }
    }
    // for(int i = 0;i<n;i++){
        // for(int j =0 ;j<k;j++)cout<<dp[i][j]<<' ';cout<<endl;
    //     for(int j = 0;j<k;j++)cout<<vals[i][j].fs.fs<<' '<<vals[i][j].fs.sc<<',';cout<<endl;
    // }
    ll ans = 0;
    for(int i = 0;i<k;i++)ans = mad(ans,dp[n-1][i]);
    cout<<ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 5 ms 1236 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 5 ms 1244 KB Output is correct
5 Correct 5 ms 1240 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 5 ms 1244 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1244 KB Output is correct
9 Correct 5 ms 1240 KB Output is correct
10 Correct 4 ms 1236 KB Output is correct
11 Correct 5 ms 1244 KB Output is correct
12 Correct 213 ms 6352 KB Output is correct
13 Correct 134 ms 6336 KB Output is correct
14 Correct 137 ms 6328 KB Output is correct
15 Correct 170 ms 6284 KB Output is correct
16 Correct 182 ms 6368 KB Output is correct
17 Correct 147 ms 6320 KB Output is correct
18 Correct 194 ms 6456 KB Output is correct
19 Correct 145 ms 6352 KB Output is correct
20 Correct 148 ms 6288 KB Output is correct
21 Correct 155 ms 6372 KB Output is correct
22 Correct 179 ms 6348 KB Output is correct