結果
問題 | No.767 配られたジャパリまん |
ユーザー |
![]() |
提出日時 | 2018-12-25 23:13:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,604 ms / 2,000 ms |
コード長 | 3,172 bytes |
コンパイル時間 | 1,970 ms |
コンパイル使用メモリ | 181,276 KB |
実行使用メモリ | 14,500 KB |
最終ジャッジ日時 | 2024-10-01 14:37:10 |
合計ジャッジ時間 | 7,710 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define fst(t) std::get<0>(t)#define snd(t) std::get<1>(t)#define thd(t) std::get<2>(t)#define unless(p) if(!(p))#define until(p) while(!(p))using ll = long long;using P = std::tuple<int,int>;const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};template <typename T>T expt(T a, T n, T mod = std::numeric_limits<T>::max()){T res = 1;while(n){if(n & 1){res = res * a % mod;}a = a * a % mod;n >>= 1;}return res;}template <typename T>T inverse(T n, T mod){return expt(n, mod-2, mod);}template <typename T>struct Combination{T mod;std::vector<T> fact, inv;Combination() = default;Combination(int max_n, T mod) : mod(mod) {fact = std::vector<T>(max_n);inv = std::vector<T>(max_n);fact[0] = 1;inv[0] = 1;for(int i=1;i<max_n;i++){fact[i] = fact[i-1] * i % mod;inv[i] = inverse(fact[i], mod);}}Combination(Combination const &) = default;Combination(Combination&&) = default;Combination& operator=(Combination const &) = default;Combination& operator=(Combination&&) = default;T nPr(T n, T r, T mod = std::numeric_limits<T>::max()){if(n < r){return 0;}return fact[n] * inv[n-r] % mod;}T nCk(T n, T k, T mod = std::numeric_limits<T>::max()){if(n < k){return 0;}return fact[n] * inv[k] % mod * inv[n-k] % mod;}T nHk(T n, T k, T mod = std::numeric_limits<T>::max()){if(n == 0 && k == 0){return 1;}return nCk(n+k-1, k);}};constexpr ll MOD = 100000007;int H, W, K;P ps[30];ll cnts[1<<20];Combination<ll> comb(200100, MOD);int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cin >> H >> W >> K;for(int i=0;i<K;++i){std::cin >> fst(ps[i]) >> snd(ps[i]);}for(int i=1;i<(1<<K);++i){std::vector<P> v;v.emplace_back(0, 0);v.emplace_back(H, W);for(int j=0;j<K;++j){if(i >> j & 1){v.emplace_back(ps[j]);}}std::sort(v.begin(), v.end());int x1, y1;std::tie(x1, y1) = v[0];ll cnt = 1;for(int j=1;j<v.size();++j){int x2, y2;std::tie(x2, y2) = v[j];unless(x1 <= x2 && y1 <= y2){cnt = 0;break;}cnt = cnt * comb.nCk((x2 - x1) + (y2 - y1), x2 - x1, MOD) % MOD;x1 = x2;y1 = y2;}cnts[i] = cnt;}for(int i=0;i<K;++i){for(int j=0;j<(1<<K);++j){if(j >> i & 1){cnts[j] = (cnts[j] + MOD - cnts[j ^ (1 << i)]) % MOD;}}}ll all = comb.nCk(H + W, H, MOD);for(int i=0;i<(1<<K);++i){ll cnt = __builtin_popcount(i) % 2 > 0 ? cnts[i] : (MOD - cnts[i]) % MOD;ll cnt2 = (all + MOD - cnt) % MOD;std::cout << cnt2 << std::endl;}}