oj.uz

Submission #709959

# Submission time Handle Problem Language Result Execution time Memory
709959 2023-03-15T01:44:26 Z pcc Trener (COCI20_trener) C++14
0 / 110
 3 ms 728 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,31};
pair<pll,pll> vals[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;
        b>>=1;
    }
    return re;
}
ll inv(ll k){
    return pw(k,mod-2);
}
ll mad(ll a,ll b){
    a += b;
    if(a>=mod)a -= mod;
    return a;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        pll tmp = {0,0};
        pll coef = {1,1};
        for(int j = 0;j<k;j++){
            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;
            }
            auto t1 = tmp;
            t1.fs = (t1.fs+mod-(s[0]-'a'+1))*inv(p.fs)%mod;
            t1.sc = (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;
        }
    }
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -