結果
問題 | No.435 占い(Extra) |
ユーザー |
![]() |
提出日時 | 2019-05-09 06:21:34 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,050 bytes |
コンパイル時間 | 973 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 50,432 KB |
最終ジャッジ日時 | 2024-10-08 12:28:10 |
合計ジャッジ時間 | 3,986 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 WA * 3 MLE * 2 |
コンパイルメッセージ
main.c: In function 'in': main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 8 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:16:24: note: in expansion of macro 'gc' 16 | int n = 0, c = gc(); | ^~ main.c: In function 'main': main.c:9:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 9 | #define pc(c) putchar_unlocked(c) | ^~~~~~~~~~~~~~~~ main.c:76:17: note: in expansion of macro 'pc' 76 | pc('0'+s), pc('\n'); | ^~
ソースコード
// yukicoder: No.435 占い(Extra)// 2019.5.10 bal4u#include <stdio.h>#include <string.h>#if 1#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[ 5000003][2]; int id = -1;char t[10000003];int inv[10] = {0,1,5,0,7,2,0,4,8,0}; // mod9 の逆数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;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;for (i = 1; i <= n; i++) {k = next();if (k < '9') s += k * t[i]; // 入力数列の各数字と二項係数の積}s %= 9;if (s == 0) s = 9; // 0以外の数列の数字根は0を9に読み替える}pc('0'+s), pc('\n');}return 0;}