// yukicoder: No.435 占い(Extra) // 2019.5.10 bal4u #include #include #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { int n = 0, c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } #define MOD 9 int 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^r return 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が含まれるので、二項係数は0 else 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のみの入力数列は数字根が0 else { 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; }