Submission #6327

#	Time	Username	Problem	Language	Result	Execution time	Memory
6327		jhs7jhs	없는 등수 찾기 (GA7_rank)	C++98	100 / 100	268 ms	2496 KiB

rank

#include<stdio.h>

int n,m;
long long man[300][2]={{0}};
long long dp[300][300]={{0}},dp2[300][300]={{0}};
int main()
{
    long long MD = 1000000007;
    long long p,q,r,ans=0,all=1;
    int i,j,k,ra;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&man[i][0],&man[i][1]);
        all *= (man[i][1] - man[i][0] + 1);
        all %= MD;
    }
    scanf("%d",&ra);
    if(ra == 1){
        printf("0\n");
        return 0;
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            for(k=0;k<ra;k++) dp[j][k] = dp2[j][k] = 0;
        }
        p = ((man[1][1]<i)?0:((man[1][0]>=i)?(man[1][1]-man[1][0]+1):(man[1][1]-i+1)));
        q = ((man[1][0]>=i)?0:((man[1][1]<i)?(man[1][1]-man[1][0]+1):(i-man[1][0])));
        r = ((man[1][1]<i+1)?0:((man[1][0]>=i+1)?(man[1][1]-man[1][0]+1):(man[1][1]-i)));
        dp[1][0] = q%MD, dp[1][1] = p%MD;
        dp2[1][0] = q%MD, dp2[1][1] = r%MD;
        for(j=2;j<=n;j++){
            p = ((man[j][1]<i)?0:((man[j][0]>=i)?(man[j][1]-man[j][0]+1):(man[j][1]-i+1)));
            q = ((man[j][0]>=i)?0:((man[j][1]<i)?(man[j][1]-man[j][0]+1):(i-man[j][0])));
            r = ((man[j][1]<i+1)?0:((man[j][0]>=i+1)?(man[j][1]-man[j][0]+1):(man[j][1]-i)));
            for(k=0;k<=j && k<ra;k++){
                dp[j][k] = (dp[j-1][k] * q % MD + ((k)?(dp[j-1][k-1] * p % MD):0))%MD;
                dp2[j][k] = (dp2[j-1][k] * q % MD + ((k)?(dp2[j-1][k-1] * r % MD):0))%MD;
            }
        }
        ans += (dp[n][ra-1]-((i==m)?0:dp2[n][ra-1]));
        while(ans<0) ans += MD;
        ans %= MD;
    }
    ans = all - ans;
    while(ans < 0) ans += MD;
    printf("%lld\n",ans);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40