結果
問題 | No.435 占い(Extra) |
ユーザー | r_dream0 |
提出日時 | 2017-02-21 21:04:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,473 bytes |
コンパイル時間 | 705 ms |
コンパイル使用メモリ | 73,712 KB |
実行使用メモリ | 65,280 KB |
最終ジャッジ日時 | 2024-04-17 02:56:04 |
合計ジャッジ時間 | 8,560 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
26,016 KB |
testcase_01 | AC | 78 ms
26,168 KB |
testcase_02 | AC | 78 ms
26,112 KB |
testcase_03 | AC | 79 ms
26,112 KB |
testcase_04 | AC | 78 ms
26,072 KB |
testcase_05 | AC | 78 ms
26,112 KB |
testcase_06 | AC | 81 ms
26,064 KB |
testcase_07 | AC | 78 ms
25,984 KB |
testcase_08 | AC | 79 ms
26,164 KB |
testcase_09 | AC | 78 ms
25,984 KB |
testcase_10 | AC | 80 ms
26,368 KB |
testcase_11 | AC | 80 ms
26,112 KB |
testcase_12 | AC | 99 ms
29,916 KB |
testcase_13 | AC | 97 ms
26,452 KB |
testcase_14 | AC | 97 ms
26,080 KB |
testcase_15 | AC | 100 ms
25,984 KB |
testcase_16 | AC | 132 ms
26,112 KB |
testcase_17 | AC | 430 ms
26,152 KB |
testcase_18 | AC | 97 ms
29,952 KB |
testcase_19 | AC | 95 ms
26,448 KB |
testcase_20 | MLE | - |
testcase_21 | AC | 260 ms
29,952 KB |
testcase_22 | AC | 252 ms
26,712 KB |
testcase_23 | AC | 258 ms
26,112 KB |
testcase_24 | AC | 290 ms
26,096 KB |
testcase_25 | AC | 604 ms
26,172 KB |
testcase_26 | MLE | - |
testcase_27 | AC | 263 ms
29,968 KB |
testcase_28 | AC | 80 ms
25,984 KB |
testcase_29 | AC | 259 ms
29,940 KB |
testcase_30 | MLE | - |
testcase_31 | AC | 233 ms
44,632 KB |
testcase_32 | AC | 243 ms
33,092 KB |
testcase_33 | AC | 276 ms
26,396 KB |
testcase_34 | AC | 406 ms
26,432 KB |
testcase_35 | AC | 263 ms
27,756 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; const int MAX_N = 10000001; // (3n)! = 3^thress[n]k (kは3の倍数ではない) vector<int> threes; vector<char> fact; vector<int> inv; void init() { threes.resize((MAX_N + 2) / 3); threes[0] = 0; for(size_t i = 1; i < threes.size(); i++) { size_t j = i * 3; threes[i] = threes[i - 1]; while(j % 3 == 0) { threes[i]++; j /= 3; } } fact.resize(MAX_N); fact[0] = 1; for(size_t i = 1; i < fact.size(); i++) { int j = i; while(j % 3 == 0) j /= 3; fact[i] = (fact[i - 1] * j) % 9; } inv.resize(9); for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { if(i * j % 9 == 1) inv[i] = j; } } } int comb(int n, int k) { int t = threes[n/3] - threes[(n - k) / 3] - threes[k / 3]; if(t >= 2) return 0; int ret = fact[n] * inv[fact[n - k]] * inv[fact[k]] % 9; if(t == 1) ret = ret * 3 % 9; return ret; } int main() { init(); int T; cin >> T; for(int i = 0; i < T; i++) { int n, x, a, b, m; cin >> n >> x >> a >> b >> m; vector<int> S(n); S[0] = x; for(int j = 1; j < n; j++) { S[j] = ((S[j - 1] ^ a) + b) % m; } for(int j = 0; j < n; j++) { S[j] %= 10; } bool allzero = true; int ans = 0; for(int i = 0; i < n; i++) { ans = (ans + S[i] * comb(n - 1, i)) % 9; if(S[i])allzero = false; } if(ans == 0 && !allzero) ans = 9; cout << ans << endl; } }