結果

問題 No.767 配られたジャパリまん
ユーザー kriii
提出日時 2018-12-15 00:20:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 162 ms / 2,000 ms
コード長 1,341 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 47,024 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-09-25 05:29:20
合計ジャッジ時間 2,122 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0