結果

問題 No.767 配られたジャパリまん
ユーザー kriiikriii
提出日時 2018-12-15 00:24:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 1,341 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 49,312 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-09-25 05:29:05
合計ジャッジ時間 2,137 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
7,808 KB
testcase_01 AC 12 ms
7,680 KB
testcase_02 AC 12 ms
7,808 KB
testcase_03 AC 11 ms
7,808 KB
testcase_04 AC 12 ms
7,936 KB
testcase_05 AC 21 ms
8,320 KB
testcase_06 AC 12 ms
7,808 KB
testcase_07 AC 12 ms
7,680 KB
testcase_08 AC 12 ms
7,680 KB
testcase_09 AC 12 ms
7,808 KB
testcase_10 AC 17 ms
8,064 KB
testcase_11 AC 12 ms
7,680 KB
testcase_12 AC 12 ms
7,808 KB
testcase_13 AC 17 ms
7,936 KB
testcase_14 AC 12 ms
7,808 KB
testcase_15 AC 12 ms
7,808 KB
testcase_16 AC 13 ms
7,808 KB
testcase_17 AC 12 ms
7,808 KB
testcase_18 AC 12 ms
7,808 KB
testcase_19 AC 13 ms
7,808 KB
testcase_20 AC 165 ms
16,000 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <algorithm>

const long long mod = 100000007;
int H,W,K;
struct pt{
	int x,y,i;
	bool operator <(const pt &t) const{
		if (x != t.x) return x < t.x;
		return y < t.y;
	}
}P[22];

long long inv[200100] = {0,1}, fact[200100] = {1,1}, ifact[200100] = {1,1};
long long D[1<<20];

long long comb(int a, int b)
{
	return fact[a+b] * ifact[a] % mod * ifact[b] % mod;
}

void go(int i, int b, long long c)
{
	if (i == K){
		D[b] = (D[b] + c) % mod;
	}
	else{
		for (int j=i;j<K;j++) if (P[i-1].x <= P[j].x && P[i-1].y <= P[j].y){
			int nb = b;
			if (P[j].i >= 0) nb ^= 1 << P[j].i;
			go(j+1,nb,c*comb(P[j].x-P[i-1].x,P[j].y-P[i-1].y)%mod);
		}
	}
}

void dnc(int l, int r)
{
	if (l + 1 == r) return;

	int m = (l + r) / 2;
	dnc(l,m);
	dnc(m,r);
	for (int i=l,j=m;i<m;i++,j++) D[i] = (D[i] + mod - D[j]) % mod;
	for (int i=l,j=m;i<m;i++,j++) D[j] = (D[j] + D[i]) % mod;
}

int main()
{
	for (int i=2;i<200100;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	scanf ("%d %d %d",&H,&W,&K);
	int all = (1 << K);
	for (int i=0;i<K;i++){
		scanf ("%d %d",&P[i].x,&P[i].y);
		P[i].i = i;
	}
	P[K++] = {0,0,-1};
	P[K++] = {H,W,-1};
	std::sort(P,P+K);

	go(1,0,1);
	dnc(0,all);

	for (int i=all-1;i>=0;i--) printf ("%lld\n",D[i]);

	return 0;
}
0