oj.uz

Submission #14229

# Submission time Handle Problem Language Result Execution time Memory
14229 2015-05-05T12:22:20 Z gs14004 선다형 시험 (TOKI14_multiple) C++14
100 / 100
 576 ms 32632 KB 
#include <cstdio>
#include <cstring>
const int mod = 1e9 + 7;
typedef long long lint;

int n, p, q;
char sa[2005], sb[2005];
char tab[2005][6];

lint bino[2005][2005];
lint dp1[2][2005];
lint dp2[2][2005];
lint dp3[2][2005];
lint dp4[2][2005];

int p1, p2, p3, p4;

void solve(){
    int cnt_amatch = 0;
    int cnt_bmatch = 0;
    int cnt_abmatch = 0;
    int cnt_samematch = 0;
    lint nomatch = 1;
    dp1[0][0] = dp2[0][0] = dp3[0][0] = dp4[0][0] = 1;
    for (int i=0; i<n; i++) {
        int p = 0;
        for (int j=0; j<5; j++) {
            if(tab[i][j] != '.') p++;
        }
        if(tab[i][sa[i] - 'a'] != '.' && sa[i] == sb[i]){
            cnt_samematch++;
            p1 ^= 1;
            dp1[p1][0] = 1;
            for (int j=1; j<=i+1; j++) {
                dp1[p1][j] = dp1[p1^1][j-1] * (p-1) + dp1[p1^1][j];
                dp1[p1][j] %= mod;
            }
        }
        else if(tab[i][sa[i] - 'a'] != '.' && tab[i][sb[i] - 'a'] != '.'){
            cnt_abmatch++;
            p2 ^= 1;
            dp2[p2][0] = 1;
            for (int j=1; j<=i+1; j++) {
                dp2[p2][j] = dp2[p2^1][j-1] * (p-2) + dp2[p2^1][j];
                dp2[p2][j] %= mod;
            }
        }
        else if(tab[i][sa[i] - 'a'] != '.'){
            cnt_amatch++;
            p3 ^= 1;
            dp3[p3][0] = 1;
            for (int j=1; j<=i+1; j++) {
                dp3[p3][j] = dp3[p3^1][j-1] * (p-1) + dp3[p3^1][j];
                dp3[p3][j] %= mod;
            }
        }
        else if(tab[i][sb[i] - 'a'] != '.'){
            cnt_bmatch++;
            p4 ^= 1;
            dp4[p4][0] = 1;
            for (int j=1; j<=i; j++) {
                dp4[p4][j] = dp4[p4^1][j-1] * (p-1) + dp4[p4^1][j];
                dp4[p4][j] %= mod;
            }
        }
        else{
            nomatch *= p;
            nomatch %= mod;
        }
    }
    for (int i=0; i<=n; i++) {
        bino[i][0] = 1;
        for (int j=1; j<=i; j++) {
            bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
            bino[i][j] %= mod;
        }
    }
    lint ret = 0;
    for (int i=0; i<=cnt_samematch; i++) {
        for (int j=i; j<=cnt_abmatch+i; j++) {
            for (int k=i; j + k <= cnt_abmatch + 2 * i; k++) {
                if(p < j || q < k || p - cnt_amatch > j || q - cnt_bmatch > k) continue;                lint t = 1;
                t *= dp1[p1][cnt_samematch - i];
                t %= mod;
                t *= dp2[p2][cnt_abmatch - j - k + 2 * i];
                t %= mod;
                t *= dp3[p3][cnt_amatch - p + j];
                t %= mod;
                t *= dp4[p4][cnt_bmatch - q + k];
                t %= mod;
                t *= bino[j + k - 2 * i][j - i];
                t %= mod;
                ret += t;
                ret %= mod;
            }
        }
    }
    ret *= nomatch;
    ret %= mod;
    printf("%lld",ret);
}

void what_the_fuck(){
    char str[10];
    scanf("%d %d %d",&n,&p,&q);
    for (int i=0; i<n; i++) {
        scanf("%s",str);
        sa[i] = str[0];
    }
    for (int i=0; i<n; i++) {
        scanf("%s",str);
        sb[i] = str[0];
    }
    for (int i=0; i<n; i++) {
        scanf("%s",tab[i]);
    }
    solve();
}

int main(){
    what_the_fuck();
    puts("");
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 32632 KB Output is correct
2 Correct 0 ms 32632 KB Output is correct
3 Correct 0 ms 32632 KB Output is correct
4 Correct 0 ms 32632 KB Output is correct
5 Correct 0 ms 32632 KB Output is correct
6 Correct 0 ms 32632 KB Output is correct
7 Correct 0 ms 32632 KB Output is correct
8 Correct 0 ms 32632 KB Output is correct
9 Correct 0 ms 32632 KB Output is correct
10 Correct 0 ms 32632 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 32632 KB Output is correct
2 Correct 0 ms 32632 KB Output is correct
3 Correct 0 ms 32632 KB Output is correct
4 Correct 17 ms 32632 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 32632 KB Output is correct
2 Correct 18 ms 32632 KB Output is correct
3 Correct 66 ms 32632 KB Output is correct
4 Correct 105 ms 32632 KB Output is correct
5 Correct 82 ms 32632 KB Output is correct
6 Correct 192 ms 32632 KB Output is correct
7 Correct 206 ms 32632 KB Output is correct
8 Correct 81 ms 32632 KB Output is correct
9 Correct 576 ms 32632 KB Output is correct
10 Correct 219 ms 32632 KB Output is correct