結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
|
提出日時 | 2023-02-03 22:56:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,191 ms / 4,000 ms |
コード長 | 2,030 bytes |
コンパイル時間 | 685 ms |
コンパイル使用メモリ | 81,656 KB |
実行使用メモリ | 84,892 KB |
最終ジャッジ日時 | 2024-07-02 21:02:48 |
合計ジャッジ時間 | 52,212 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
import sysfrom collections import deque, Counterinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353class Combinatorics():def __init__(self, mod, maxi):self.mod = modself.maxi = maxiself.facs = [1] * (maxi + 1)self.factinvs = [1] * (maxi + 1)self.invs = [1] * (maxi + 1)for i in range(2, self.maxi + 1):self.facs[i] = ((self.facs[i-1] * i) % self.mod)self.invs[i] = (-self.invs[self.mod % i] * (self.mod // i)) % self.modself.factinvs[i] = (self.factinvs[i-1] * self.invs[i]) % self.moddef choose(self, n, k) -> int:if k < 0 or k > n: return 0if k == 0 or k == n: return 1k = min(k, n - k)return (((self.facs[n] * self.factinvs[k]) % self.mod) * self.factinvs[n-k]) % self.moddef perm(self, n, k) -> int:return (self.choose(n, k) * self.facs[k]) % self.moddef homop(self, n, k) -> int:if n == k == 0:return 1return self.choose(n + k - 1, k)t = 500maxi = 2 * 10 ** 5C = Combinatorics(mod, maxi)pre = [[0] * (maxi // t + 1) for _ in range(maxi // t + 1)]for i in range(0, maxi + 1, t):for j in range(0, maxi + 1, t):if j // t > 0:pre[i // t][j // t] += pre[i // t][j // t - 1]for k in range(j - t + 1, j + 1):pre[i // t][j // t] += C.choose(i, k)else:pre[i//t][j//t] = 1def Csum(n, k):nnow = (n // t) * tknow = (k // t) * tnow = pre[n // t][k // t]for i in range(n - nnow):now = 2 * now - C.choose(nnow + i, know)now %= modfor i in range(k - know):now = now + C.choose(n, know + i + 1)now %= modreturn nowdef solve():n, m = mi()ans = Csum(n - 1, m - 1) * (pow(2, n, mod) - 1)ans %= modprint(ans)for _ in range(ii()):solve()