結果

問題 No.1392 Don't be together
ユーザー 👑 SPD_9X2
提出日時 2021-02-12 23:08:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,272 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 89,956 KB
最終ジャッジ日時 2024-07-20 00:37:54
合計ジャッジ時間 4,145 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 2 WA * 1 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
#1392
n
11
使
M
NM
M
http://aozoragakuen.sakura.ne.jp/betukai/node26.html
nM
(M-1)^n + (-1)^n * (M-1)
"""
import sys
from sys import stdin
mod = 998244353
def modfac(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
def modnCr(n,r,mod,fac,inv): #facinvs(nn)
return fac[n] * inv[n-r] * inv[r] % mod
def f(n,m): #nm
if m <= 1:
return 0
elif m == 2:
if n % 2 == 0:
return 2
else:
return 0
else:
return ( pow(M-1,n,mod) + pow(-1,n,mod) * (M-1) ) % mod
fac,inv = modfac(100000,mod)
N,M = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))
for i in range(N):
A[i] -= 1
lis = []
end = [False] * N
for i in range(N):
if not end[i]:
v = A[i]
lis.append(1)
end[v] = True
while v != i:
lis[-1] += 1
v = A[v]
end[v] = True
print (lis,file=sys.stderr)
dp = [1] * (M+1)
for i in range(M+1):
for j in lis:
dp[i] *= f(j,i)
dp[i] *= inv[i]
dp[i] %= mod
#print (dp)
ans = 0
dp.reverse()
for i in range(M+1):
if i % 2 == 0:
ans += dp[i]
else:
ans -= dp[i]
print (ans % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0