結果
問題 | No.2083 OR Subset |
ユーザー | taiga0629kyopro |
提出日時 | 2022-08-31 11:25:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,424 ms / 3,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 469,120 KB |
最終ジャッジ日時 | 2024-11-08 02:34:55 |
合計ジャッジ時間 | 14,564 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
60,544 KB |
testcase_01 | AC | 50 ms
60,416 KB |
testcase_02 | AC | 77 ms
76,096 KB |
testcase_03 | AC | 760 ms
285,188 KB |
testcase_04 | AC | 444 ms
191,568 KB |
testcase_05 | AC | 1,291 ms
431,492 KB |
testcase_06 | AC | 398 ms
178,176 KB |
testcase_07 | AC | 124 ms
86,484 KB |
testcase_08 | AC | 138 ms
92,388 KB |
testcase_09 | AC | 745 ms
284,272 KB |
testcase_10 | AC | 507 ms
209,852 KB |
testcase_11 | AC | 320 ms
154,172 KB |
testcase_12 | AC | 224 ms
124,928 KB |
testcase_13 | AC | 1,398 ms
464,560 KB |
testcase_14 | AC | 1,359 ms
453,880 KB |
testcase_15 | AC | 1,378 ms
456,916 KB |
testcase_16 | AC | 1,402 ms
465,588 KB |
testcase_17 | AC | 1,417 ms
465,212 KB |
testcase_18 | AC | 50 ms
60,544 KB |
testcase_19 | AC | 1,424 ms
469,120 KB |
ソースコード
############################# ############# cnb_max=10**5 mod=998244353 ############# kai=[1]*(cnb_max+1) rkai=[1]*(cnb_max+1) for i in range(cnb_max): kai[i+1]=kai[i]*(i+1)%mod rkai[cnb_max]=pow(kai[cnb_max],mod-2,mod) for i in range(cnb_max): rkai[cnb_max-1-i]=rkai[cnb_max-i]*(cnb_max-i)%mod def cnb(x,y): if y>x: return 0 if x<0:return 0 if y<0:return 0 return (kai[x]*rkai[y]%mod)*rkai[x-y]%mod def inv(n): return kai[n-1]*rkai[n]%mod ################################## def sol1(n): #O(N^3) dp=[[0]*(n+1) for i in range(n+1)] dp[0][0]=1 for i in range(1,n+1): for j in range(n+1): for cnti in range(1,n+1): if j-cnti<0:continue dp[i][j]+=dp[i-1][j-cnti]*cnb(n-(j-cnti),cnti) dp[i][j]%=mod def f(k): if k==0:return 1 ans=0 for s in range(1,n+1): ans+=dp[k][s]*pow((pow(2,k,mod)-k)%mod,n-s,mod) ans%=mod return ans ans=0 for k in range(n+1): ans+=f(k)*rkai[k] ans%=mod return ans def sol2(n): #O(N^2) def _(i, j): if min(i, j) < 0: return -1 return i * (n+2) + j num = [0] * (n+2) ** 2 st = [0] * (n+2) ** 2 for k in range(1, n+1): nod = pow(2, k, mod) - k nod %= mod num[_(k, 0)] = 1 for i in range(1, n+1): num[_(k, i)] = num[_(k, i - 1)] * nod % mod st[_(0, 0)] = 1 for i in range(1, n+1): for j in range(1, i + 1): st[_(i, j)] = st[_(i - 1, j - 1)] + st[_(i - 1, j)] * j st[_(i, j)] %= mod ans=1 for k in range(1,n+1): for m in range(k,n+1): res=cnb(n,m)*st[_(m,k)]%mod res*=num[_(k,n-m)] ans+=res ans%=mod return ans%mod s=[] fs={0} def naive(n): u=[i for i in range(1,2**n)] ans=[0] def dfs(i): global fs if i==len(u): ans[0]+=1 return dfs(i+1) if True: bffs={x for x in fs} for x in bffs: fs.add(x|u[i]) s.append(u[i]) if len(fs)==2**(len(s)):dfs(i+1) s.pop() fs={x for x in bffs} return dfs(0) return ans[0] n=int(input()) print(sol2(n))