結果
問題 | No.1392 Don't be together |
ユーザー | chineristAC |
提出日時 | 2021-01-24 14:06:35 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,353 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 87,260 KB |
実行使用メモリ | 174,716 KB |
最終ジャッジ日時 | 2023-08-30 21:34:58 |
合計ジャッジ時間 | 16,681 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 85 ms
80,728 KB |
testcase_01 | AC | 86 ms
80,728 KB |
testcase_02 | AC | 86 ms
80,716 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 86 ms
80,704 KB |
testcase_06 | AC | 528 ms
116,204 KB |
testcase_07 | WA | - |
testcase_08 | AC | 770 ms
133,896 KB |
testcase_09 | AC | 1,387 ms
174,716 KB |
testcase_10 | AC | 580 ms
120,768 KB |
testcase_11 | AC | 848 ms
142,484 KB |
testcase_12 | AC | 542 ms
117,636 KB |
testcase_13 | AC | 705 ms
131,920 KB |
testcase_14 | AC | 764 ms
137,600 KB |
testcase_15 | AC | 572 ms
121,640 KB |
testcase_16 | AC | 840 ms
146,520 KB |
testcase_17 | AC | 601 ms
124,788 KB |
testcase_18 | AC | 745 ms
136,424 KB |
testcase_19 | AC | 687 ms
135,188 KB |
testcase_20 | AC | 357 ms
95,008 KB |
testcase_21 | AC | 216 ms
85,596 KB |
testcase_22 | AC | 498 ms
110,248 KB |
testcase_23 | AC | 377 ms
96,932 KB |
testcase_24 | AC | 268 ms
90,780 KB |
testcase_25 | AC | 406 ms
100,488 KB |
testcase_26 | AC | 194 ms
84,976 KB |
testcase_27 | AC | 236 ms
88,532 KB |
testcase_28 | AC | 436 ms
99,756 KB |
testcase_29 | AC | 284 ms
89,672 KB |
ソースコード
def cmb(n, r, mod):#コンビネーションの高速計算 if ( r<0 or r>n ): return 0 r = min(r, n-r) return g1[n] * g2[r] * g2[n-r] % mod mod = 998244353 #出力の制限 N = 2*10**5 g1 = [1]*(N+1) # 元テーブル g2 = [1]*(N+1) #逆元テーブル inverse = [1]*(N+1) #逆元テーブル計算用テーブル for i in range( 2, N + 1 ): g1[i]=( ( g1[i-1] * i ) % mod ) inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod ) g2[i]=( (g2[i-1] * inverse[i]) % mod ) inverse[0]=0 N,M = map(int,input().split()) P = list(map(int,input().split())) P = [P[i]-1 for i in range(N)] cycle = [] used = [False]*N for i in range(N): if not used[i]: used[i] = True c = 1 pos = i while not used[P[pos]]: pos = P[pos] used[pos] = True c += 1 cycle.append(c) n = len(cycle) res = 0 for k in range(2,M+1): dp = [[0,0] for i in range(N+1)] dp[0][0] = 1 for i in range(1,N): dp[i][0] += dp[i-1][1] dp[i][1] += dp[i-1][0] * max(0,k-1) + dp[i-1][1] * max(0,k-2) dp[i][0] %= mod dp[i][1] %= mod tmp = 1 for l in cycle: tmp *= dp[l][0] * k tmp %= mod if (M-k)%2: res -= cmb(M,k,mod) * tmp else: res += cmb(M,k,mod) * tmp res %= mod print(res*g2[M] % mod)