Submission #123221


Source Code Expand

Copy
#include <cstdlib>
#include <cstring>
#include <memory>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)

#define FOR(x,to) for(x=0;x<to;x++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ZERO(a) memset(a,0,sizeof(a))
void _fill_int(int* p,int val,int rep) {int i;	FOR(i,rep) p[i]=val;}
#define FILL_INT(a,val) _fill_int((int*)a,val,sizeof(a)/4)
#define MINUS(a) _fill_int((int*)a,-1,sizeof(a)/4)
ll GETi() { ll i;scanf("%lld",&i); return i;}
//-------------------------------------------------------

ll mo=1000000007;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

/*
ll testtest(int L,vector<int> C,int lele) {
	ll ret=0;
	int x,y,z,t;
	
	if(C.size()==0) {
		ret += comb(lele,L);
	}
	else if(C.size()==1) {
		for(x=1;x<=C[0];x++)  {
			ret += (ret + comb(C[0],x)*comb(lele,L-x)%mo) % mo;
		}
	}
	else if(C.size()==2) {
		for(x=1;x<=C[0];x++) for(y=1;y<=C[1];y++) {
			ret = (ret+comb(C[0],x)*comb(C[1],y)%mo*comb(lele,L-x-y)%mo)%mo;
		}
	}
	else if(C.size()==3) {
		for(x=1;x<=C[0];x++) for(y=1;y<=C[1];y++) for(z=1;z<=C[2];z++)  {
			ret = (ret + comb(C[0],x)*comb(C[1],y)%mo*comb(C[2],z)%mo*comb(lele,L-x-y-z)%mo)%mo;
		}
	}
	else if(C.size()==4) {
		for(x=1;x<=C[0];x++) for(y=1;y<=C[1];y++) for(z=1;z<=C[2];z++) for(t=1;t<=C[3];t++) {
			ret = (ret + comb(C[0],x)*comb(C[1],y)%mo*comb(C[2],z)%mo*comb(C[3],t)%mo*comb(lele,L-x-y-z-t)%mo)%mo;
		}
	}
	
	return ret%mo;
}

ll test2(int x,int y,ll N) {
	ll ret=0;
	int lele=max(0,(x-2)*(y-2));
	
	for(int mask=0;mask<1<<9;mask++) {
		if(mask&(1<<4)) continue;
		
		if(x<2 && ((mask&(1<<2)) || (mask&(1<<5)) || (mask&(1<<8)))) continue;
		if(x<3 && ((mask&(1<<1)) || (mask&(1<<4)) || (mask&(1<<7)))) continue;
		if(y<2 && ((mask&(1<<6)) || (mask&(1<<7)) || (mask&(1<<8)))) continue;
		if(y<3 && ((mask&(1<<3)) || (mask&(1<<4)) || (mask&(1<<5)))) continue;
		
		if((mask&(1<<0))==0 && (y>=3 && (mask&(1<<3))==0) && (y>=2 && (mask&(1<<6))==0)) continue; // L
		if((mask&(1<<2))==0 && (y>=3 && (mask&(1<<5))==0) && (y>=2 && (mask&(1<<8))==0) && x>=2) continue; // R
		if((mask&(1<<0))==0 && (x>=3 && (mask&(1<<1))==0) && (x>=2 && (mask&(1<<2))==0)) continue; // T
		if((mask&(1<<6))==0 && (x>=3 && (mask&(1<<7))==0) && (x>=2 && (mask&(1<<8))==0) && y>=2) continue; // B
		
		int ll=N;
		// kado
		if(mask&(1<<0)) ll--;
		if(mask&(1<<2)) ll--;
		if(mask&(1<<6)) ll--;
		if(mask&(1<<8)) ll--;
		
		vector<int> can;
		if(mask&(1<<1)) can.push_back(x-2);
		if(mask&(1<<7)) can.push_back(x-2);
		if(mask&(1<<3)) can.push_back(y-2);
		if(mask&(1<<5)) can.push_back(y-2);
		
		ret += testtest(ll,can,lele);
	}
	return ret%mo;
}

int N;
ll memo[32][32];

ll test(int x,int y) {
	
	if(x<=0 || y<=0) return 0;
	if(x*y<N) return memo[x][y]=0;
	if(x*y==N) return memo[x][y]=1;
	if(memo[x][y]>=0) return memo[x][y];
	return memo[x][y]=(4*mo+comb(x*y,N)-2*test(x,y-1)-2*test(x-1,y)+test(x-1,y-1))%mo;
	
}
*/



void solve() {
	int f,i,j,k,l,x,y;
	int H,W,X,Y,D,L;
	
	cin>>H>>W;
	cin>>X>>Y;
	cin>>D>>L;
	
	ll res=(H-X+1)*(W-Y+1);
	res = res*comb(D+L,L) % mo;
	ll tm=0;
	for(int mask=0;mask<16;mask++) {
		x=X,y=Y;
		if(mask&1) x--;
		if(mask&2) x--;
		if(mask&4) y--;
		if(mask&8) y--;
		if(x<0 || y<0) continue;
		if(__builtin_popcount(mask)%2) tm-=comb(x*y,D+L);
		else tm+=comb(x*y,D+L);
	}
	res=(res*(tm%mo))%mo;
	
	_P("%lld\n",res);
}


int main(int argc,char** argv){
	string s;
	for(int i=1;i<argc;i++) s+=argv[i],s+='\n';
	for(int i=s.size()-1;i>=0;i--) ungetc(s[i],stdin);
	solve();
	return 0;
}

Submission Info

Submission Time
Task D - AtCoder社の冬
User kmjp
Language C++ (G++ 4.6.4)
Score 100
Code Size 4145 Byte
Status
Exec Time 46 ms
Memory 7964 KB

Compile Error

./Main.cpp: In function ‘ll GETi()’:
./Main.cpp:29:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Test Cases

Set Name Score / Max Score Test Cases
sub 100 / 100 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, test_03E.txt, test_04E.txt, test_07E.txt, test_08E.txt, test_11E.txt, test_12E.txt, test_15E.txt, test_16E.txt, test_19E.txt, test_20E.txt, test_23E.txt, test_24E.txt, test_27E.txt, test_28E.txt, test_31E.txt, test_32E.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_45E.txt, test_47E.txt
All 0 / 1 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03E.txt, test_04E.txt, test_05.txt, test_06.txt, test_07E.txt, test_08E.txt, test_09.txt, test_10.txt, test_11E.txt, test_12E.txt, test_13.txt, test_14.txt, test_15E.txt, test_16E.txt, test_17.txt, test_18.txt, test_19E.txt, test_20E.txt, test_21.txt, test_22.txt, test_23E.txt, test_24E.txt, test_25.txt, test_26.txt, test_27E.txt, test_28E.txt, test_29.txt, test_30.txt, test_31E.txt, test_32E.txt, test_33.txt, test_34.txt, test_35.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45E.txt, test_46.txt, test_47E.txt, test_48.txt
Case Name Status Exec Time Memory
00_sample_01E.txt 46 ms 7844 KB
00_sample_02E.txt 41 ms 7852 KB
00_sample_03E.txt 39 ms 7856 KB
00_sample_04.txt 42 ms 7944 KB
test_01.txt 40 ms 7852 KB
test_02.txt 43 ms 7828 KB
test_03E.txt 39 ms 7960 KB
test_04E.txt 40 ms 7848 KB
test_05.txt 40 ms 7848 KB
test_06.txt 40 ms 7852 KB
test_07E.txt 39 ms 7844 KB
test_08E.txt 40 ms 7964 KB
test_09.txt 38 ms 7848 KB
test_10.txt 40 ms 7852 KB
test_11E.txt 40 ms 7940 KB
test_12E.txt 39 ms 7844 KB
test_13.txt 38 ms 7856 KB
test_14.txt 38 ms 7852 KB
test_15E.txt 38 ms 7852 KB
test_16E.txt 39 ms 7852 KB
test_17.txt 38 ms 7848 KB
test_18.txt 37 ms 7844 KB
test_19E.txt 39 ms 7848 KB
test_20E.txt 38 ms 7848 KB
test_21.txt 39 ms 7848 KB
test_22.txt 39 ms 7844 KB
test_23E.txt 40 ms 7848 KB
test_24E.txt 39 ms 7848 KB
test_25.txt 40 ms 7852 KB
test_26.txt 39 ms 7852 KB
test_27E.txt 38 ms 7844 KB
test_28E.txt 39 ms 7852 KB
test_29.txt 42 ms 7840 KB
test_30.txt 42 ms 7836 KB
test_31E.txt 39 ms 7852 KB
test_32E.txt 41 ms 7852 KB
test_33.txt 39 ms 7852 KB
test_34.txt 40 ms 7856 KB
test_35.txt 38 ms 7844 KB
test_36E.txt 40 ms 7852 KB
test_37E.txt 39 ms 7856 KB
test_38E.txt 38 ms 7844 KB
test_39E.txt 38 ms 7840 KB
test_40.txt 39 ms 7852 KB
test_41.txt 38 ms 7852 KB
test_42.txt 40 ms 7852 KB
test_43.txt 38 ms 7952 KB
test_44.txt 41 ms 7848 KB
test_45E.txt 38 ms 7852 KB
test_46.txt 39 ms 7856 KB
test_47E.txt 39 ms 7848 KB
test_48.txt 39 ms 7940 KB