結果

問題 No.723 2つの数の和
ユーザー NatsubiSoganNatsubiSogan
提出日時 2021-02-15 12:46:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,798 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 121,736 KB
最終ジャッジ日時 2024-07-23 00:20:49
合計ジャッジ時間 13,704 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 439 ms
89,148 KB
testcase_01 AC 431 ms
89,124 KB
testcase_02 AC 435 ms
89,116 KB
testcase_03 AC 468 ms
108,064 KB
testcase_04 AC 474 ms
114,900 KB
testcase_05 AC 469 ms
113,436 KB
testcase_06 AC 474 ms
113,396 KB
testcase_07 AC 449 ms
98,412 KB
testcase_08 AC 455 ms
99,956 KB
testcase_09 AC 471 ms
114,748 KB
testcase_10 AC 453 ms
97,844 KB
testcase_11 AC 442 ms
89,820 KB
testcase_12 AC 486 ms
102,556 KB
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 445 ms
89,404 KB
testcase_21 AC 442 ms
88,988 KB
testcase_22 AC 439 ms
88,844 KB
testcase_23 AC 473 ms
121,736 KB
testcase_24 AC 449 ms
95,500 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#拡張Euclidの互除法
from collections import Counter


def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g

#mod p における逆元
def invmod(a, p):
    x, y, g = extgcd(a, p)
    x %= p
    return x

class NumberTheoreticTransform:
    def primitive_root(self, m):
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [0] * 20
        divs[0] = 2
        cnt = 1
        x = (m - 1) // 2
        while x % 2 == 0: x //= 2
        i = 3
        while i ** 2 <= x:
            if x % i == 0:
                divs[cnt] = i
                cnt += 1
                while x % i == 0: x //= i
        if x > 1:
            divs[cnt] = x
            cnt += 1
        g = 2
        while True:
            f = True
            for i in range(cnt):
                if pow(g, (m - 1) // divs[i], m) == 1: break
            else:
                return g
            g += 1

    def bsf(self, x):
        res = 0
        while x % 2 == 0:
            res += 1
            x //= 2
        return res

    def __init__(self, mod):
        self.mod = mod
        self.g = self.primitive_root(self.mod)

    def butterfly(self, a):
        n = len(a)
        h = (n - 1).bit_length()
        sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497)
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p] * now % self.mod
                    a[i + offset] = (l + r) % self.mod
                    a[i + offset + p] = (l - r) % self.mod
                now = now * sum_e[(~s & -~s).bit_length() - 1] % self.mod

    def butterfly_inv(self, a):
        n = len(a)
        h = (n - 1).bit_length()
        sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951)
        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l + r) % self.mod
                    a[i + offset + p] = (l - r) * inow % self.mod
                inow = inow * sum_ie[(~s & -~s).bit_length() - 1] % self.mod

    def convolution(self, a, b):
        n = len(a)
        m = len(b)
        if not a or not b: return []
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.butterfly(a)
        self.butterfly(b)
        c = [0] * z
        for i in range(z):
            c[i] = a[i] * b[i] % self.mod
        self.butterfly_inv(c)
        iz = invmod(z, self.mod)
        for i in range(n + m - 1):
            c[i] = c[i] * iz % self.mod
        return c[:n + m - 1]
    

class FormalPowerSeries:
    def __init__(self, n, l = [], mod = 998244353):
        self.n = n
        self.l = l + [0] * (n - len(l))
        self.mod = mod
    
    def add(self, other):
        res = FormalPowerSeries(self.n, [], self.mod)
        for i in range(self.n):
            res.l[i] = self.l[i] + other.l[i]
            res.l[i] %= self.mod
        return res
    
    def subtract(self, other):
        res = FormalPowerSeries(self.n, [], self.mod)
        for i in range(self.n):
            res.l[i] = self.l[i] - other.l[i]
            res.l[i] %= self.mod
        return res

    def multiply(self, other):
        res = FormalPowerSeries(self.n * 2, [], self.mod)
        NTT = NumberTheoreticTransform(self.mod)
        cv = NTT.convolution(self.l, other.l)
        for i in range(len(cv)):
            res.l[i] = cv[i]
        return res
    
    def resize(self, n):
        res = FormalPowerSeries(n, [], self.mod)
        for i in range(min(n, self.n)):
            res.l[i] = self.l[i]
        return res

    def times(self, k):
        res = FormalPowerSeries(self.n, [], self.mod)
        for i in range(self.n):
            res.l[i] = self.l[i] * k % self.mod
        return res

    def inverse(self):
        r = invmod(self.l[0], self.mod)
        m = 1
        res = FormalPowerSeries(m, [r], self.mod)
        while m < self.n:
            m *= 2
            res = res.resize(m)
            res = res.times(2).subtract(res.multiply(res.resize(m)).multiply(self.resize(m)))
        res = res.resize(self.n)
        return res

    def divide(self, other):
        self.multiply(self, other.inverse())

    def differentiate(self):
        res = FormalPowerSeries(self.n, [], self.mod)
        for i in range(1, self.n):
            res.l[i - 1] = self.l[i] * i % self.mod
        return res

    def integrate(self):
        res = FormalPowerSeries(self.n, [], self.mod)
        for i in range(self.n - 1):
            res.l[i + 1] = self.l[i] * invmod(i + 1, self.mod)
        return res

n, x = map(int, input().split())
a = list(map(int, input().split()))
d = dict(Counter(a))
l = [0] * (10 ** 5 + 10)
for k, v in d.items():
    l[k] = v
a = FormalPowerSeries(10 ** 5 + 10, l)
print(a.multiply(a.resize(10 ** 5 + 10)).l[x])
0