oj.uz

답안 #223240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223240 2020-04-15T05:58:44 Z dantoh000 Trener (COCI20_trener) C++14
0 / 110
 83 ms 12604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int n,k;
ll KEY = 999997;
ll f[55];
int v[26];
unordered_map<ll,int> ct;
ll HASH(string s){
    ll res = 0;
    for (int i = 0; i < s.size(); i++){
        res = ((res*KEY) + v[s[i]-'a'])%mod;
    }
    return res;
}
ll a[55][1505];
int dp[2][1505];
bool can(ll a, ll b, int len){
    for (int i = 0; i < 26; i++){
        if ((a*KEY + v[i])%mod == b || (a + i*f[len])%mod == b) return true;
    }
    return false;
}
int main(){
    iota(v,v+26,1);
    random_shuffle(v,v+26);
    //for (int i = 0; i < 26; i++) printf("%d ",v[i]);
    f[0] = 1;
    for (int i = 1; i <= 50; i++){
        f[i] = (f[i-1]*KEY)%mod;
    }
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            string s;
            cin >> s;
            a[i][j] = HASH(s);
            //cout << s << " " << a[i][j] << endl;
        }
    }
    for (int i = 1; i <= k; i++) {
        ct[a[n][i]]++;
    }
    for (int i = n-1; i >= 1; i--){
        for (int j = 1; j <= k; j++){
            ll res = 0;
            for (int T = 1; T <= 26; T++){
                //printf("%lld -> %lld %lld\n",a[i][j],(a[i][j]*KEY + T)%mod,(a[i][j] + T*f[i])%mod);
                res += ct[(a[i][j]*KEY + T)%mod];
                if ((a[i][j] + T*f[i])%mod != (a[i][j]*KEY + T)%mod) res += ct[(a[i][j] + T*f[i])%mod];
            }
            dp[i&1][j] = res%mod;
            ct[a[i][j]] += res%mod;
            ct[a[i][j]] %= mod;
        }
        for (int j = 1; j <= k; j++){
            ct[a[i+1][j]] += mod-dp[1-i&1][k];
            ct[a[i+1][j]] %= mod;
        }
    }
    int sum = 0;
    for (int i = 1; i <= k; i++) {
        sum += ct[a[1][i]];
        sum %= mod;
    }
    printf("%d",sum);
}

Compilation message

trener.cpp: In function 'll HASH(std::__cxx11::string)':
trener.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++){
                     ~~^~~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:58:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             ct[a[i+1][j]] += mod-dp[1-i&1][k];
                                     ~^~
trener.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 12604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -