結果
問題 | No.2083 OR Subset |
ユーザー | taiga0629kyopro |
提出日時 | 2022-08-31 11:25:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,149 ms / 3,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 437 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 469,272 KB |
最終ジャッジ日時 | 2024-04-25 15:31:24 |
合計ジャッジ時間 | 12,300 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
61,284 KB |
testcase_01 | AC | 46 ms
62,560 KB |
testcase_02 | AC | 72 ms
76,424 KB |
testcase_03 | AC | 657 ms
285,820 KB |
testcase_04 | AC | 393 ms
191,696 KB |
testcase_05 | AC | 1,095 ms
431,560 KB |
testcase_06 | AC | 359 ms
178,144 KB |
testcase_07 | AC | 119 ms
86,492 KB |
testcase_08 | AC | 133 ms
92,376 KB |
testcase_09 | AC | 622 ms
284,736 KB |
testcase_10 | AC | 449 ms
210,216 KB |
testcase_11 | AC | 297 ms
154,324 KB |
testcase_12 | AC | 218 ms
125,068 KB |
testcase_13 | AC | 1,144 ms
464,704 KB |
testcase_14 | AC | 1,109 ms
453,800 KB |
testcase_15 | AC | 1,118 ms
456,868 KB |
testcase_16 | AC | 1,149 ms
465,592 KB |
testcase_17 | AC | 1,126 ms
465,132 KB |
testcase_18 | AC | 46 ms
61,588 KB |
testcase_19 | AC | 1,145 ms
469,272 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))