Submission #709963

#	Time	Username	Problem	Language	Result	Execution time	Memory
709963		pcc	Trener (COCI20_trener)	C++14	22 / 110	4 ms	948 KiB

trener

#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));
                tmp.sc = mad(tmp.sc,coef.sc*(i-'a'+1));
                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 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55