結果

問題 No.2817 Competition
コンテスト
ユーザー minimum
提出日時 2024-07-19 23:10:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,172 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 199,504 KB
最終ジャッジ日時 2024-07-19 23:10:42
合計ジャッジ時間 4,273 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def primitive_root(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 = [2]
    x = (m - 1) // 2
    while (x % 2 == 0): 
        x //= 2
    i = 3
    while i * i <= x:
        if x % i == 0:
            divs.append(i)
            while x % i == 0: 
                x //= i
        i += 2
    if x > 1: divs.append(x)
    g = 2
    while 1:
        if all(pow(g, (m - 1) // d, m) != 1 for d in divs): 
            return g
        g += 1

class Convolution:
    
    def __init__(self, MOD = 998244353):
        self.MOD = MOD
        self.g = primitive_root(self.MOD)
        self.sum_e = []
        self.sum_ie = []
        es = [0] * 30
        ies = [0] * 30
        cnt2 = self.bsf(self.MOD - 1)
        e = pow(self.g, (self.MOD - 1) >> cnt2, self.MOD)
        ie = pow(e, self.MOD - 2, self.MOD)
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e *= e
            e %= self.MOD
            ie *= ie
            ie %= self.MOD
        now = 1
        inow = 1
        for i in range(cnt2 - 1):
            self.sum_e.append((es[i] * now) % self.MOD)
            now *= ies[i]
            now %= self.MOD
            self.sum_ie.append((ies[i] * inow) % self.MOD)
            inow *= es[i]
            inow %= self.MOD
    
    def butterfly(self, a):
        n = len(a)
        h = self.ceil_pow2(n)
        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
                    a[i + offset] = (l + r) % self.MOD
                    a[i + offset + p] = (l - r) % self.MOD
                now *= self.sum_e[self.bsf(~s)]
                now %= self.MOD
        return a
    
    def butterfly_inv(self, a):
        n = len(a)
        h = self.ceil_pow2(n)
        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 *= self.sum_ie[self.bsf(~s)]
                inow %= self.MOD
        return a

    def convolution(self, a, b):
        n = len(a)
        m = len(b)
        if n == 0 or m == 0:
            return []
        if min(n, m) <= 60:
            if n < m:
                n, m = m, n
                a, b = b, a
            ans = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    ans[i + j] += a[i] * b[j]
                    ans[i + j] %= self.MOD
            return ans
        z = 1 << self.ceil_pow2(n + m - 1)
        for _ in range(z - n):
            a.append(0)
        for _ in range(z - m):
            b.append(0)
        a = self.butterfly(a)
        b = self.butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= self.MOD
        a = self.butterfly_inv(a)[:n + m - 1]
        iz = pow(z, self.MOD - 2, self.MOD)
        a = [(ai * iz) % self.MOD for ai in a]
        return a
    
    def bsf(self, x):
        ans = 0
        t = 1
        while x & t == 0:
            ans += 1
            t <<= 1
        return ans

    def ceil_pow2(self, x):
        return (x - 1).bit_length() if x != 1 else 0


MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
conv = Convolution(MOD)


fs = [[1, A[i]] for i in range(N)]

for i in range(70):
    l = 0
    r = l + (1 << i)
    while r < N:
        fs[l] = conv.convolution(fs[l], fs[r])
        l += (1 << (i + 1))
        r = l + (1 << i)

ans = 0
for k in range(1, N + 1):
    ans += fs[0][k] * pow(k, N - k, MOD)
    ans %= MOD
    # print(fs[0][k] * pow(k, N - k, MOD))
print(ans)
0