結果
問題 | No.1646 Avoid Palindrome |
ユーザー |
👑 |
提出日時 | 2021-08-13 22:48:33 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 482 ms / 3,000 ms |
コード長 | 2,374 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 5,504 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 15:50:06 |
合計ジャッジ時間 | 13,938 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
local mfl, mce = math.floor, math.ceillocal mod = 998244353local n = io.read("*n", "*l")local s = io.read()local t = {}for i = 1, n dot[i] = s:sub(i, i)if t[i] == "?" thent[i] = falseelset[i] = t[i]:byte() - 96endendfor i = 1, n - 1 doif t[i] and t[i] == t[i + 1] thenprint(0) os.exit()endendfor i = 1, n - 2 doif t[i] and t[i] == t[i + 2] thenprint(0) os.exit()endendif n == 1 thenprint(t[1] and 1 or 26) os.exit()endlocal dp1, dp2 = {}, {}if not t[1] and not t[2] thenfor i = 1, 26 do for j = 1, 26 dolocal v = (i - 1) * 26 + jdp1[v] = i == j and 0 or 1end endelseif not t[1] thenlocal i2 = t[2]for i = 1, 26 do for j = 1, 26 dolocal v = (i - 1) * 26 + jif i == i2 or j ~= i2 thendp1[v] = 0elsedp1[v] = 1endend endelseif not t[2] thenlocal i1 = t[1]for i = 1, 26 do for j = 1, 26 dolocal v = (i - 1) * 26 + jif i ~= i1 or j == i1 thendp1[v] = 0elsedp1[v] = 1endend endelselocal i1 = t[1]local i2 = t[2]for i = 1, 26 do for j = 1, 26 dolocal v = (i - 1) * 26 + jif i ~= i1 or j ~= i2 thendp1[v] = 0elsedp1[v] = 1endend endendfor i = 3, n dolocal src = i % 2 == 1 and dp1 or dp2local dst = i % 2 == 1 and dp2 or dp1for j = 1, 676 do dst[j] = 0 endif t[i] thenlocal z = t[i]for prvprv = 1, 26 doif prvprv ~= z thenfor prv = 1, 26 doif prv ~= z thenlocal d = (prv - 1) * 26 + zdst[d] = dst[d] + src[(prvprv - 1) * 26 + prv]endendendendelselocal row = {}local col = {}for j = 1, 26 do row[j], col[j] = 0, 0 endlocal all = 0for j = 1, 26 dofor k = 1, 26 dolocal sz = src[(j - 1) * 26 + k]all = all + szrow[j] = row[j] + szcol[k] = col[k] + szendendlocal z = t[i]for j = 1, 26 dofor prv = 1, 26 doif prv ~= j thenlocal v = col[prv] - src[(j - 1) * 26 + prv]local d = (prv - 1) * 26 + jdst[d] = vendendendendfor j = 1, 676 do dst[j] = dst[j] % mod endendlocal tbl = n % 2 == 1 and dp2 or dp1local ret = 0for i = 1, 676 doret = ret + tbl[i]endprint(ret % mod)-- print(os.clock())