結果

問題 No.767 配られたジャパリまん
コンテスト
ユーザー nebukuro09
提出日時 2018-12-15 17:55:57
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,742 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,124 ms
コンパイル使用メモリ 190,452 KB
最終ジャッジ日時 2025-01-06 19:30:55
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:66:9: error: reference to ‘any’ is ambiguous
   66 |         any[mask] = __builtin_popcount(mask) % 2 ? -all[mask] : all[mask];
      |         ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:77,
                 from main.cpp:1:
/usr/include/c++/13/any:80:9: note: candidates are: ‘class std::any’
   80 |   class any
      |         ^~~
main.cpp:15:4: note:                 ‘ll any [1048576]’
   15 | ll any[1<<20];
      |    ^~~
main.cpp:70:9: error: reference to ‘any’ is ambiguous
   70 |         any[mask] += any[mask ^ (1 << i)];
      |         ^~~
/usr/include/c++/13/any:80:9: note: candidates are: ‘class std::any’
   80 |   class any
      |         ^~~
main.cpp:15:4: note:                 ‘ll any [1048576]’
   15 | ll any[1<<20];
      |    ^~~
main.cpp:70:22: error: reference to ‘any’ is ambiguous
   70 |         any[mask] += any[mask ^ (1 << i)];
      |                      ^~~
/usr/include/c++/13/any:80:9: note: candidates are: ‘class std::any’
   80 |   class any
      |         ^~~
main.cpp:15:4: note:                 ‘ll any [1048576]’
   15 | ll any[1<<20];
      |    ^~~
main.cpp:71:9: error: reference to ‘any’ is ambiguous
   71 |         any[mask] %= MOD;
      |         ^~~
/usr/include/c++/13/any:80:9: note: candidates are: ‘class std::any’
   80 |   class any
      |         ^~~
main.cpp:15:4: note:                 ‘ll any [1048576]’
   15 | ll any[1<<20];
      |    ^~~
main.cpp:75:18: error: reference to ‘any’ is ambiguous
   75 |         cout << (any[mask] % MOD + MOD) % MOD << "\n";
      |                  ^~~
/usr/include/c++/13/any:80:9: note: candidates are: ‘class std::any’
   80 |   class any
      |         ^~~
main.cpp:15:4: note:                 ‘ll any [1048576]’
   15 | ll any[1<<20];
      |    ^~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

const ll MOD = 100000007;
const ll MAX = 200010;

int H, W, K;
vector<ll> P[22];
ll F[MAX];
ll all[1<<20];
ll any[1<<20];


ll powmod(ll a, ll x, ll m) {
    ll ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

ll comb(ll n, ll r) {
    if (n < r) return 0;
    return F[n] * powmod(F[n-r], MOD-2, MOD) % MOD * powmod(F[r], MOD-2, MOD) % MOD;
}


void solve() {
    cin >> H >> W >> K;
    REP(i, K) {
        P[i] = {0, 0, i};
        cin >> P[i][0] >> P[i][1];
    }

    F[0] = 1;
    REP2(i, 1, MAX) F[i] = F[i-1] * i % MOD;
    all[0] = comb(H+W, H);

    REP2(mask, 1, 1<<K) {
        vector<vector<ll>> A;
        A.push_back({0, 0, -1});
        A.push_back({H, W, -1});
        REP(i, K) if ((mask & (1<<P[i][2]))) A.push_back(P[i]);
        sort(A.begin(), A.end());

        ll tmp = 1;
        REP(i, (int)A.size()-1) {
            if (A[i][1] > A[i+1][1]) {
                tmp = 0;
                break;
            }
            tmp *= comb(A[i+1][0] - A[i][0] + A[i+1][1] - A[i][1], A[i+1][0] - A[i][0]);
            tmp %= MOD;
        }

        all[mask] = tmp;
    }

    REP(mask, 1<<K) {
        any[mask] = __builtin_popcount(mask) % 2 ? -all[mask] : all[mask];
    }

    REP(i, K) REP(mask, 1<<K) if (mask & (1 << i)) {
        any[mask] += any[mask ^ (1 << i)];
        any[mask] %= MOD;
    }

    REP(mask, 1<<K) {
        cout << (any[mask] % MOD + MOD) % MOD << "\n";
    }

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    solve();
}
0