Submission #4857

#	Time	Username	Problem	Language	Result	Execution time	Memory
4857		cki86201	Energetic turtle (IZhO11_turtle)	C++98	80 / 100	234 ms	5424 KiB

turtle

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;
typedef pair<int,int> Pi;
#define X first
#define Y second

int prime[50000],len;
bool chk[600060];
int num[50000];
int N,M,K,T,Z;
int data[1<<20],R[20];

int f(int x,int p)
{
	int ret = 0;
	while(x)x/=p, ret += x;
	return ret;
}

int comb(int n,int r)
{
	int i;
	for(i=0;i<len;i++)num[i]=0;
	for(i=0;i<len;i++){
		num[i] += f(n+r,prime[i]) - f(n,prime[i]) - f(r,prime[i]);
	}
	ll ret = 1;
	for(i=0;i<len;i++){
		for(int j=0;j<num[i];j++)ret *= prime[i], ret %= Z;
	}
	return (int)ret;
}

Pi inp[22];
int dis2[22][22],dis1[2][22];

bool comp(const Pi &a,const Pi &b){return a.X!=b.X?a.X<b.X:a.Y<b.Y;}

int nCr(int n,int r)
{
	int i, ret=1;
	for(i=1;i<=r;i++)ret*=(n-i+1), ret/=i;
	return ret;
}

inline int setbits(int x)
{
	x=x-((x>>1)&0x55555555);
	x=(x&0x33333333)+((x>>2)&0x33333333);
	return(((x+(x>>4))&0x0F0F0F0F)*0x01010101)>>24;
}

void mod(ll &x)
{
	if(x >= 0)x %= Z;
	else{
		int tmp = -x / Z + 2;
		x = (x + tmp*Z) % Z;
	}
}

int main(){
	scanf("%d%d%d%d%d",&N,&M,&K,&T,&Z);
	int i;
	for(i=2;i<=N+M;i++){
		if(chk[i])continue;
		prime[len++] = i;
		for(int j=i<<1;j<=N+M;j+=i)chk[j]=1;
	}
	for(i=0;i<K;i++)scanf("%d%d",&inp[i].X,&inp[i].Y);
	sort(inp,inp+K);
	for(i=0;i<K;i++){
		dis1[0][i] = comb(inp[i].X, inp[i].Y);
		dis1[1][i] = comb(N - inp[i].X, M - inp[i].Y);
	}
	for(i=0;i<K;i++){
		for(int j=i+1;j<K;j++){
			if(inp[j].Y >= inp[i].Y)dis2[i][j] = comb(inp[j].X-inp[i].X, inp[j].Y-inp[i].Y);
			else dis2[i][j] = -1;
		}
	}
	data[0] = 1;
	for(i=0;i<K;i++)data[1<<i] = dis1[0][i];
	for(int b=3;b<1<<K;b++){
		if(b==17){
			b++;
			b--;
		}
		int bit1 = K-1;
		while(!(1<<bit1&b))bit1--;
		if(1<<bit1 == b)continue;
		int bit2 = bit1-1;
		while(!(1<<bit2&b))bit2--;
		if(dis2[bit2][bit1] == -1)continue;
		data[b] = (int)(((ll)data[b^1<<bit1] * dis2[bit2][bit1]) % Z);
	}
	R[0] = data[0] = comb(N,M);
	for(int b=1;b<1<<K;b++){
		int bit1 = K-1;
		while(!(1<<bit1&b))bit1--;
		int sb = setbits(b);
		R[sb] += (int)(((ll)data[b] * dis1[1][bit1]) % Z);
		R[sb] %= Z;
	}
	ll ans = 0;
	for(i=0;i<=T;i++){
		int t = 1;
		for(int j=i;j<=K;j++){
			ans += (ll)t * nCr(j,i) * R[j];
			mod(ans);
			t *= -1;
		}
	}
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'int main()':
turtle.cpp:67:7: 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:74:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<K;i++)scanf("%d%d",&inp[i].X,&inp[i].Y);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100