結果
問題 | No.435 占い(Extra) |
ユーザー |
![]() |
提出日時 | 2020-01-20 17:03:26 |
言語 | C (gcc 13.3.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,250 bytes |
コンパイル時間 | 414 ms |
コンパイル使用メモリ | 32,384 KB |
実行使用メモリ | 51,408 KB |
最終ジャッジ日時 | 2024-10-08 12:32:54 |
合計ジャッジ時間 | 3,736 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 MLE * 2 |
ソースコード
// yukicoder: No.435 占い(Extra)// 2019.5.10 bal4u#include <stdio.h>#include <string.h>#if 1int getchar_unlocked(void);int putchar_unlocked(int c);#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endifint in(){int n = 0, c = gc();do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');return n;}#define MOD 9int tbl[10000003][2]; int id = -1;char t[10000003];int inv[10] = {0,1,5,0,7,2,0,4,8,0}; // mod9 の逆数//int inv[10] = {0,6,5,0,4,1,0,2,3,0};int p3(int *a, int n) { // 3のべき乗を取り出すint r = 0;while (n % 3 == 0) r++, n /= 3;*a = n; // *a は3のべき乗以外に残った部分 元のn = (*a) * 3^rreturn r;}void calcBC(int n){int i, a, b, _n;tbl[0][0] = 1, tbl[0][1] = 0, t[0] = 1;if (n == 0) return;tbl[1][1] = p3(&a, n), tbl[1][0] = a % MOD, t[1] = n % MOD;_n = n >> 1;for (i = 2; i <= _n; i++) {tbl[i][1] = tbl[i-1][1] + p3(&a, n+1-i) - p3(&b, i); // 3のべき乗tbl[i][0] = (tbl[i-1][0] * a * inv[(b % MOD)]) % MOD; // 3のべき乗以外の部分if (tbl[i][1] >= 2) t[i] = 0; // 9が含まれるので、二項係数は0else if (tbl[i][1] == 0) t[i] = tbl[i][0]; // そのままが二項係数else t[i] = tbl[i][0]*3 % MOD; // 3をかけて二項係数になる}for (; i <= n; i++) t[i] = t[n-i]; // 後半の計算は前半を流用}int x, a, b, m;int next() { // つぎの入力数字x = ((x^a) + b) % m;return x % 10;}int main(){int i, k, n, s, T;int zero;T = in();while (T--) {n = in()-1, x = in(), a = in(), b = in(), m = in();if (m == 1 || (x|a|b) == 0) s = 0; // 0のみの入力数列は数字根が0else {if (id != n) calcBC(n), id = n; // 数列をすべて違う長さの入力データには本解答プログラムは無力s = x % 10;zero = (s == 0);for (i = 1; i <= n; i++) {k = next();if (k) {zero = 0;if (k < '9') s += k * t[i]; // 入力数列の各数字と二項係数の積}}if (zero) s = 0;else {s %= 9;if (s == 0) s = 9; // 0以外の数列の数字根は0を9に読み替える}}pc('0'+s), pc('\n');}return 0;}