結果

問題 No.1195 数え上げを愛したい（文字列編）
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:37:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,070 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 97,352 KB
最終ジャッジ日時 2025-03-20 20:38:14
合計ジャッジ時間 8,945 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    s = sys.stdin.read().strip()
    from collections import Counter
    cnt = Counter(s)
    
    # 计算阶乘和逆元，最多到总长度
    max_n = len(s)
    fact = [1] * (max_n + 1)
    for i in range(1, max_n+1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1]*(max_n+1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # 初始化多项式，初始为1（0次项）
    poly = [1]
    for c, m in cnt.items():
        # 当前字符的生成函数是sum_{k=0}^m x^k /k!
        # 转换为多项式: sum_0^m x^k /k! ，将其加入poly的乘积
        # 需要将poly与当前的生成函数相乘
        # 这个生成函数的各项是 1/(k!)，相乘时要合并到多项式中
        # 但用我们的转换方式，poly中的每个元素a_j表示 sum的系数，而之后每个a_j会被视为乘以j!后的值
        
        new_poly = [0]*(len(poly) + m)
        # 对于当前poly中的每一个次数j，将其与当前字符的生成函数做卷积
        for j in range(len(poly)):
            if poly[j] == 0:
                continue
            # 当前项是 poly[j]对应j!的系数，即在当前多项式中的项是 (poly[j] * x^j )
            # 生成当前字符的generating function是 sum_{k=0}^m x^k /k!
            # 当乘上这个多项式时，每个term会是 x^{j+k} * (poly[j] / (k!))
            # 现在，我们将poly视为存储的是 sum a_j / j! x^j。这样乘积的系数为 a_j / j! * 1/k! ，合并后的系数为 (a_j * ) ... ?
            # 这可能需要重新调整存储方式，使得 poly中的 a_j 表示系数，即真正的生成函数的项是 a_j x^j，而对应的是原来的生成函数中的项为 x^j/(j!).
            # 因此，当前的poly已经存储了 a_j x^j，其中原来的系数是 a_j = prev_poly的乘积后的系数，实际对应的项是 a_j x^j，而每个x^j 实际代表的是原来的项 x^j/j!， 但在此时，我们需要将每个字符的生成函数视为 sum_{k=0}^m x^k/k!，这相当于新的多项式将乘法的 sum_{k=0}^m x^k/k!。
            # 在这种表示下，poly的每个元素的积压积需要加上k的terms， where each term is new_poly[j+k] += poly[j] * (1/k! )
            
            for k in range(0, m+1):
                if j + k >= len(new_poly):
                    continue
                # 计算 current的贡献：poly[j] * (1/k! )
                term = poly[j] * inv_fact[k] % MOD
                new_poly[j + k] = (new_poly[j + k] + term) % MOD
        poly = new_poly
    
    # 现在，poly中的每个项coeff是各个生成函数乘积后的x^j的系数。真实生成函数的项是 x^j/(j!)，所以总和需要计算 sum (coeff_j * j! )
    result = 0
    for j in range(len(poly)):
        if j ==0:
            continue
        res_j = poly[j] * fact[j] % MOD
        result = (result + res_j) % MOD
    print(result)
    
    
if __name__ == "__main__":
    main()
0