結果
問題 | No.767 配られたジャパリまん |
ユーザー |
|
提出日時 | 2018-04-28 19:23:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,559 bytes |
コンパイル時間 | 1,111 ms |
コンパイル使用メモリ | 83,272 KB |
実行使用メモリ | 14,812 KB |
最終ジャッジ日時 | 2024-09-25 04:45:14 |
合計ジャッジ時間 | 4,425 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 6 |
other | WA * 15 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>using namespace std;#define mod long(1e9 + 7)#define bitcount(n) __builtin_popcount(n)struct position{int y, x;bool operator <(const position another) const{return y < another.y;}};long power(long base, int exponent){if(exponent % 2){return power(base, exponent - 1) * base % mod;}else if(exponent){long root_ans = power(base, exponent / 2);return root_ans * root_ans % mod;}else{return 1;}}vector<long> factorial{1};vector<long> inverse_factorial{1};long move_combination(int h, int w){if(h < 0 || w < 0){return 0;}else{return factorial[h + w] * inverse_factorial[h] % mod * inverse_factorial[w] % mod;}}int main(){int H, W, K, Q;cin >> H >> W >> K >> Q;pair<position, int> friendss[K];for(int i = 0; i < K; i++){position friends;cin >> friends.y >> friends.x;friendss[i] = {friends, i};}sort(friendss, friendss + K);for(long i = 1; i <= 2e5; i++){factorial.push_back(factorial.back() * i % mod);inverse_factorial.push_back(power(factorial.back(), mod - 2));}long ans[1 << K];for(int i = 0; i < (1 << K); i++){vector<position> destination;destination.push_back({0, 0});for(int j = 0; j < K; j++){if((i >> j) & 1){destination.push_back(friendss[j].first);}}destination.push_back({H, W});long this_ans = 1;for(int j = 1; j < destination.size(); j++){this_ans *= move_combination(destination[j].y - destination[j - 1].y, destination[j].x - destination[j - 1].x);this_ans %= mod;}int i_position = 0;for(int j = 0; j < K; j++){i_position += ((i >> j) & 1) * (1 << (friendss[j].second));}if(bitcount(i) % 2){ans[i_position] = mod - this_ans;}else{ans[i_position] = this_ans;}}for(int i = 0; i < K; i++){for(int j = 0; j < (1 << K); j++){if((j >> i) & 1){ans[j] += ans[j & ~(1 << i)];ans[j] %= mod;}}}for(int i = 0; i < Q; i++){string S;cin >> S;int this_number = 0;for(int j = 0; j < K; j++){this_number += (S[j] == 'x') * (1 << j);}cout << ans[this_number] << endl;}}