oj.uz

Submission #14227

# Submission time Handle Problem Language Result Execution time Memory
14227 2015-05-05T12:09:29 Z gs14004 선다형 시험 (TOKI14_multiple) C++14
100 / 100
 559 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]){
           // printf("%d 1\n",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'] != '.'){
            //printf("%d 2\n",i);
            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'] != '.'){
          //  printf("%d 3\n",i);
            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'] != '.'){
           // printf("%d 4\n",i);
            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{
            //printf("%d 5\n",i);
            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=0; j<=cnt_abmatch; j++) {
            for (int k=0; j+k<=cnt_abmatch; k++) {
                // i -> same of match.
                // j -> a match
                // k -> b match
                // cnt_abmatch - j - k = remainder
                int pmatch = p - i - j;
                int qmatch = q - i - k;
                int rem = cnt_abmatch - j - k;
                if(pmatch < 0 || qmatch < 0 || pmatch > cnt_amatch || qmatch > cnt_bmatch) continue;
                lint t = 1;
                t *= dp1[p1][cnt_samematch - i];
                t %= mod;
                t *= dp2[p2][rem];
                t %= mod;
                t *= dp3[p3][cnt_amatch - pmatch];
                t %= mod;
                t *= dp4[p4][cnt_bmatch - qmatch];
                t %= mod;
                t *= bino[j + k][j];
                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 22 ms 32632 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32632 KB Output is correct
2 Correct 19 ms 32632 KB Output is correct
3 Correct 65 ms 32632 KB Output is correct
4 Correct 96 ms 32632 KB Output is correct
5 Correct 82 ms 32632 KB Output is correct
6 Correct 166 ms 32632 KB Output is correct
7 Correct 297 ms 32632 KB Output is correct
8 Correct 90 ms 32632 KB Output is correct
9 Correct 559 ms 32632 KB Output is correct
10 Correct 229 ms 32632 KB Output is correct