Submission #13279

#	Time	Username	Problem	Language	Result	Execution time	Memory
13279		dohyun0324	Energetic turtle (IZhO11_turtle)	C++98	75 / 100	181 ms	3320 KiB

turtle

#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[21][21],d2[21][21],dis[21][21],arr[100010],dap;
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,j;
    ll ans=1;
    for(i=1;i<=top;i++){
        arr[i]=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
        for(j=1;j<=arr[i];j++){ans*=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 (stderr)

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: 75 / 100