結果
問題 | No.767 配られたジャパリまん |
ユーザー | ミドリムシ |
提出日時 | 2018-12-13 22:50:43 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 542 ms / 2,000 ms |
コード長 | 2,382 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 72,840 KB |
実行使用メモリ | 14,932 KB |
最終ジャッジ日時 | 2024-09-25 04:45:26 |
合計ジャッジ時間 | 3,781 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
6,812 KB |
testcase_01 | AC | 61 ms
6,940 KB |
testcase_02 | AC | 61 ms
6,940 KB |
testcase_03 | AC | 61 ms
6,944 KB |
testcase_04 | AC | 61 ms
6,944 KB |
testcase_05 | AC | 90 ms
7,048 KB |
testcase_06 | AC | 61 ms
6,940 KB |
testcase_07 | AC | 61 ms
6,940 KB |
testcase_08 | AC | 62 ms
6,940 KB |
testcase_09 | AC | 61 ms
6,944 KB |
testcase_10 | AC | 75 ms
6,944 KB |
testcase_11 | AC | 62 ms
6,940 KB |
testcase_12 | AC | 62 ms
6,940 KB |
testcase_13 | AC | 74 ms
6,940 KB |
testcase_14 | AC | 61 ms
6,940 KB |
testcase_15 | AC | 61 ms
6,944 KB |
testcase_16 | AC | 63 ms
6,944 KB |
testcase_17 | AC | 61 ms
6,940 KB |
testcase_18 | AC | 61 ms
6,944 KB |
testcase_19 | AC | 63 ms
6,940 KB |
testcase_20 | AC | 542 ms
14,932 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:87:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long int’ [-Wformat=] 87 | printf("%d\n", ans[i]); | ~^ ~~~~~~ | | | | int long int | %ld
ソースコード
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define mod long(1e8 + 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; cin >> H >> W >> K; 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 < (1 << K); i++){ printf("%d\n", ans[i]); } }