oj.uz

Submission #13283

# Submission time Handle Problem Language Result Execution time Memory
13283 2015-02-09T07:36:39 Z dohyun0324 Energetic turtle (IZhO11_turtle) C++
100 / 100
 176 ms 3020 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int x,y,n,m,k,t,z,prime[100010],top,ch[600010];
ll d[23][23],d2[23][23],dis[23][23],dap,len;
struct data{
    int x,y;
    bool operator<(const data&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}a[300010];
ll cnt(int x,int p)
{
    ll c=0;
    while(x){x/=p; c+=x;}
    return c;
}
ll comb(int x,int y)
{
    int i;
    ll ans=1,j;
    for(i=1;i<=top;i++){
        len=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
        for(j=1;j<=len;j++){ans*=(ll)prime[i]; ans%=z;}
    }
    return ans;
}
int main()
{
    int i,j,r;
    scanf("%d %d %d %d %d",&n,&m,&k,&t,&z);
    for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
    a[k].x=n; a[k].y=m;
    for(i=2;i<=600000;i++){
        if(ch[i]==1) continue;
        for(j=i;j<=600000;j+=i) ch[j]=1;
        prime[++top]=i;
    }
    sort(a+1,a+k+1);
    for(i=1;i<=k;i++){
        for(j=i+1;j<=k;j++){
            if(a[j].y>=a[i].y) dis[i][j]=comb(a[j].x-a[i].x+a[j].y-a[i].y,a[j].y-a[i].y);
        }
    }
    for(i=1;i<=k;i++){
        for(j=i+1;j<=k;j++){
            d[i][j]=dis[i][j];
            for(r=i+1;r<=j;r++){
                d[i][j]-=(d[i][r]*dis[r][j])%z;
                if(d[i][j]<0) d[i][j]+=z;
            }
        }
    }
    t++; d2[1][0]=1;
    for(i=2;i<=k;i++){
        for(j=1;j<=t;j++){
            for(r=1;r<=i-1;r++){
                d2[i][j]+=d2[r][j-1]*d[r][i];
                d2[i][j]%=z;
            }
        }
    }
    for(i=1;i<=t;i++){dap+=d2[k][i]; dap%=z;}
    printf("%lld",dap);
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
     ^~~
turtle.cpp:34:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
                                                       ^
turtle.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d",&n,&m,&k,&t,&z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=k;i++) scanf("%d %d",&a[i].x,&a[i].y); k+=2;
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2908 KB Output is correct
2 Correct 23 ms 2808 KB Output is correct
3 Correct 19 ms 2940 KB Output is correct
4 Correct 60 ms 2892 KB Output is correct
5 Correct 90 ms 2892 KB Output is correct
6 Correct 57 ms 2896 KB Output is correct
7 Correct 68 ms 3020 KB Output is correct
8 Correct 45 ms 2908 KB Output is correct
9 Correct 85 ms 2896 KB Output is correct
10 Correct 71 ms 2808 KB Output is correct
11 Correct 77 ms 2892 KB Output is correct
12 Correct 107 ms 2912 KB Output is correct
13 Correct 47 ms 2900 KB Output is correct
14 Correct 123 ms 2908 KB Output is correct
15 Correct 118 ms 2900 KB Output is correct
16 Correct 113 ms 2808 KB Output is correct
17 Correct 97 ms 2808 KB Output is correct
18 Correct 172 ms 2888 KB Output is correct
19 Correct 176 ms 2960 KB Output is correct
20 Correct 98 ms 2900 KB Output is correct