题解（Python）

exec("import sys\nMOD = 998244353\ndef qpow(a, b):\n res = 1\n while b:\n if b & 1: res = res * a % MOD\n a = a * a % MOD\n b >>= 1\n return res\ninv = lambda x: qpow(x, MOD-2)\ndef get_next(s):\n n = len(s)\n nxt = [0]n\n for i in range(1, n):\n j = nxt[i-1]\n while j > 0 and s[i] != s[j]:\n j = nxt[j-1]\n if s[i] == s[j]:\n j += 1\n nxt[i] = j\n return nxt\ndef kmp_match(pat, nxt, text):\n j = 0\n for i in range(len(text)):\n while j > 0 and text[i] != pat[j]:\n j = nxt[j-1]\n if text[i] == pat[j]:\n j += 1\n return j\ndef calc_val(X, nxt_X, Y, powk):\n l = kmp_match(X, nxt_X, Y)\n res = 0\n while l > 0:\n res = (res + powk[l]) % MOD\n l = nxt_X[l-1]\n return res\ndef calc_P(S, T, n, powk):\n nxt_S = get_next(S)\n nxt_T = get_next(T)\n valSS = calc_val(S, nxt_S, S, powk)\n valTT = calc_val(T, nxt_T, T, powk)\n valST = calc_val(S, nxt_S, T, powk)\n valTS = calc_val(T, nxt_T, S, powk)\n numerator = (valTT - valST) % MOD\n denominator = (valSS + valTT - valST - valTS) % MOD\n return numerator * inv(denominator) % MOD\ndata = sys.stdin.read().split()\nit = iter(data)\ntid = int(next(it))\nt = int(next(it))\nout = []\nif tid <= 8:\n for _ in range(t):\n n = int(next(it)); k = int(next(it))\n S = [int(next(it)) for _ in range(n)]\n T = [int(next(it)) for _ in range(n)]\n powk = [1](n+1)\n for i in range(1, n+1):\n powk[i] = powk[i-1] * k % MOD\n out.append(str(calc_P(S, T, n, powk)))\nelse:\n for _ in range(t):\n n = int(next(it)); k = int(next(it))\n T = [int(next(it)) for _ in range(n)]\n powk = [1]*(n+1)\n for i in range(1, n+1):\n powk[i] = powk[i-1] * k % MOD\n c = 2 if T[0] == 1 else 1\n S2 = [c] + T-1\n out.append(' '.join(map(str, S2)))\nsys.stdout.write('\n'.join(out) + '\n')")