結果
| 問題 |
No.3123 Inversion
|
| ユーザー |
 tassei903
|
| 提出日時 | 2025-04-19 15:25:13 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,641 ms / 10,000 ms |
| コード長 | 6,511 bytes |
| コンパイル時間 | 577 ms |
| コンパイル使用メモリ | 82,060 KB |
| 実行使用メモリ | 317,432 KB |
| 最終ジャッジ日時 | 2025-04-19 15:25:59 |
| 合計ジャッジ時間 | 43,193 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
from collections import defaultdict
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members
def __str__(self):
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())
def rev(p):
n = len(p)
return tuple([p[-1-i] for i in range(n)])
def inv(p):
n = len(p)
q = [-1] * n
for i in range(n):
q[p[i]] = i
return tuple(q)
def naive1(n):
from itertools import permutations
a = []
for p in permutations(range(n), n):
a.append(p)
N = len(a)
uf = UnionFind(N)
for p in permutations(range(n), n):
uf.union(a.index(p), a.index(inv(p)))
uf.union(a.index(p), a.index(rev(p)))
ans = sum([uf.size(x) * uf.size(x) for x in uf.roots()])
b = [0] * 9
# print([uf.size(x) for x in uf.roots()])
for x in uf.roots():
b[uf.size(x)] += 1
print(b)
D = uf.all_group_members()
c = 0
for x in D:
if uf.size(x) == 2:
if inv(a[D[x][0]]) == a[D[x][0]]:
c += 1
# print(uf.size(x), [a[i] for i in D[x]])
elif uf.size(x) ==8:
continue
print([a[i] for i in D[x]])
return ans
def naive2(n):
s = set()
from itertools import permutations
from collections import Counter
ans = 0
b = [0] * 10
for p in permutations(range(n), n):
if p in s:
continue
cnt = 0
S = []
for i in range(8):
S.append(p)
if i % 2 == 0:
p = rev(p)
else:
p = inv(p)
# print(Counter(S))
cnt = len(set(S))
s |= set(S)
b[cnt] += 1
# print(p, cnt)
ans += cnt * cnt
# print(b)
return ans
def nxt(p, i):
for j in range(i):
if j % 2 == 0:
p = rev(p)
else:
p = inv(p)
return p
def naive4(n):
s = set()
from itertools import permutations
from collections import Counter
ans = 0
b = [0] * 6
for p in permutations(range(n), n):
if p in s:
continue
cnt = 0
S = []
for i in range(8):
S.append(p)
if i % 2 == 0:
p = rev(p)
else:
p = inv(p)
# print(Counter(S))
cnt = len(set(S))
s |= set(S)
if cnt == 1:
b[0] += cnt
elif cnt == 2 and S[0] == S[2]:
# print(S)
b[1] += cnt
elif cnt == 2:
# print(S)
b[2] += cnt
elif cnt == 4 and (S[0] == S[-1] or S[0] == S[3]):
b[3] += cnt
# print(S)
elif cnt == 4:
b[4] += cnt
# print(S)
assert (S[0] == S[4] and S[1] == S[5])
else:
b[5] += cnt
# print(p, cnt)
ans += cnt * cnt
return b
def naive3(n):
from itertools import permutations
from math import factorial
ans = 0
b = [0] * 8
for t in range(8):
for p in permutations(range(n), n):
if nxt(p, t) == p:
b[t] += 1
# print(b)
# print(sum(b) // 8 * factorial(n))
return sum(b) // 8 * factorial(n)
def a898(n):
ans = 0
for k in range(n + 1):
ans += pow(2, k, mod) * s1(n, k) * b(k) % mod
ans %= mod
return ans
def a900(n):
return (a85(n) - a898(n//2)) * pow(2, mod-2, mod) % mod
def a902(n):
if n >= 3:
return 2 * a902(n-1) + (2 * n - 2) * a902(n - 2)
else:
return 1
# # print(naive(5), naive2(5))
# print(naive2(4))
# print(naive3(4))
# for i in range(1, 9):
# print(i, naive(i), naive2(i), naive3(i))
t, mod = na()
nn = 5 * 10 ** 6 + 10
fact = [1] * nn
for i in range(nn - 1):
fact[i + 1] = fact[i] * (i + 1) % mod
Q = [0] * nn
Q[0] = 1
Q[1] = 1
for i in range(2, nn):
Q[i] = (Q[i-1] + Q[i-2] * (i - 1) % mod) % mod
# print(Q[:10])
R = [0] * nn
R[0] = R[1] = 1
R[4] = 2
for i in range(5, nn):
if i % 4 == 0:
R[i] = R[i-4] * (i - 2) % mod
elif i % 4 == 1:
R[i] = R[i-1]
else:
R[i] = 0
G = [0] * nn
G[0] = 1
for i in range(1, nn):
if i % 2 == 1:
G[i] = G[i-1]
else:
G[i] = i * G[i-2] % mod
# print(G[:10])
B = [0] * nn
B[0] = B[1] = 1
B[2] = B[3] = 2
for i in range(4, nn):
if i % 2 == 1:
B[i] = B[i-1]
else:
B[i] = (2 * B[i-2] + (i - 2) * B[i-4]) % mod
# print(B[:10])
# for _ in range(t):
# n = ni()
# print(naive(n))
# for i in range(1, 10):
# print(Q[i], R[i], G[i], B[i], f[i])
# print(G[i] - R[i] - B[i], (Q[i] - B[i]) * 2)
ans = [0] * nn
for i in range(1, nn):
F = [0] * 6
if i == 1:
F = [1, 0, 0, 0, 0, 0]
else:
F[1] = R[i]
F[2] = B[i]
F[3] = (Q[i] - B[i]) * 2
F[4] = G[i] - R[i] - B[i]
F[5] = fact[i] - sum(F[:5])
ans[i] = F[0] * 1 + (F[1] + F[2]) * 2 + (F[3] + F[4]) * 4 + F[5] * 8
ans[i] %= mod
# print(F)
for _ in range(t):
n = ni()
print(ans[n])