結果
問題 | No.1392 Don't be together |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
"""#1392包除原理?少なくともn組が同じグループに属す分け方を数え上げればよい順列であることが対称性の面で有効に働きそう一緒にいてはいけない人を線で結んでいくとサイクルがいくつかある形になる条件を1つ採用すると、連結成分が1減るが…サイクル全体を使用してしまうと、最後の条件で連結成分が減らないMの方を包除するのはありN個をM個のグループに分割する方法は…サイクルに関してM色で塗り分けるこれは、http://aozoragakuen.sakura.ne.jp/betukai/node26.htmlこれなので、n個のサイクルをM個に分けるのは(M-1)^n + (-1)^n * (M-1)通り"""import sysfrom sys import stdinmod = 998244353def modfac(n, MOD):f = 1factorials = [1]for m in range(1, n + 1):f *= mf %= MODfactorials.append(f)inv = pow(f, MOD - 2, MOD)invs = [1] * (n + 1)invs[n] = invfor m in range(n, 1, -1):inv *= minv %= MODinvs[m - 1] = invreturn factorials, invsdef modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)return fac[n] * inv[n-r] * inv[r] % moddef f(n,m): #n個のサイクルをm色で塗り分ける場合の数if m <= 1:return 0elif m == 2:if n % 2 == 0:return 2else:return 0else:return ( pow(M-1,n,mod) + pow(-1,n,mod) * (M-1) ) % modfac,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] -= 1lis = []end = [False] * Nfor i in range(N):if not end[i]:v = A[i]lis.append(1)end[v] = Truewhile v != i:lis[-1] += 1v = A[v]end[v] = Trueprint (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 = 0dp.reverse()for i in range(M+1):if i % 2 == 0:ans += dp[i]else:ans -= dp[i]print (ans % mod)