oj.uz

답안 #223272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223272 2020-04-15T06:33:00 Z dantoh000 Trener (COCI20_trener) C++14
22 / 110
 80 ms 12556 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int n,k;
ll KEY = 31;
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 += f[i]*(s[i]-'a'+1);
    }
    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(){
    //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]]++;
        dp[n&1][i]++;
    }
    ll ans = 0;
    for (int i = n-1; i >= 1; i--){
        for (int j = 1; j <= k; j++){
            dp[i&1][j] = 0;
            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];
            }
            res %= mod;
            dp[i&1][j] = res;
            if (i != 1) {
                ct[a[i][j]] += res;
                ct[a[i][j]] %= mod;
            }
            else ans += res;
        }
        for (int j = 1; j <= k; j++){
            ct[a[i+1][j]] += mod-dp[1-i&1][j];
            ct[a[i+1][j]] %= mod;
        }
    }
    printf("%d",ans%mod);
}

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:63:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             ct[a[i+1][j]] += mod-dp[1-i&1][j];
                                     ~^~
trener.cpp:67:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
     printf("%d",ans%mod);
                 ~~~~~~~^
trener.cpp:31: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
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 12556 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 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 80 ms 12556 KB Output isn't correct
6 Halted 0 ms 0 KB -