結果

問題 No.2413 Multiple of 99
ユーザー lam6er
提出日時 2025-04-15 23:58:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,071 bytes
コンパイル時間 473 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 103,220 KB
最終ジャッジ日時 2025-04-15 23:59:38
合計ジャッジ時間 12,655 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, K = map(int, sys.stdin.readline().split())
    
    max_fact = 10**6 + 2 * 10**5
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_fact + 1)
    inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
    for i in range(max_fact - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    def comb(n, k):
        if n < 0 or k < 0 or n < k:
            return 0
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
    
    def f(c, s):
        if s < 0 or s > 9 * c:
            return 0
        res = 0
        max_k = min(c, s // 10)
        for k in range(0, max_k + 1):
            s_remain = s - 10 * k
            if s_remain < 0:
                continue
            term = comb(c, k) * comb(s_remain + c - 1, c - 1)
            if k % 2 == 1:
                term = (-term) % MOD
            res = (res + term) % MOD
        return res
    
    c_odd = (N + 1) // 2
    c_even = N // 2
    ans = 0
    
    for m in range(0, N + 1):
        s_total = 9 * m
        r = (10 * m) % 11
        s_odd_min = max(0, s_total - 9 * c_even)
        s_odd_max = min(9 * c_odd, s_total)
        if s_odd_min > s_odd_max:
            continue
        
        delta = (r - s_odd_min) % 11
        s_start = s_odd_min + delta
        if s_start < s_odd_min:
            s_start += 11
        if s_start > s_odd_max:
            continue
        
        count = 0
        s_odd = s_start
        while s_odd <= s_odd_max:
            s_even = s_total - s_odd
            if s_even < 0 or s_even > 9 * c_even:
                s_odd += 11
                continue
            a = f(c_odd, s_odd)
            b = f(c_even, s_even)
            count = (count + a * b) % MOD
            s_odd += 11
        
        if m == 0:
            pow_term = 0
        else:
            pow_term = pow(9 * m, K, MOD)
        ans = (ans + count * pow_term) % MOD
    
    print(ans % MOD)

if __name__ == '__main__':
    main()
0