結果

問題 No.2964 Obstruction Bingo
ユーザー kakel-san
提出日時 2025-01-17 00:13:51
言語 C#
(.NET 8.0.404)
結果
WA  
実行時間 -
コード長 2,385 bytes
コンパイル時間 12,401 ms
コンパイル使用メモリ 171,748 KB
実行使用メモリ 209,416 KB
最終ジャッジ日時 2025-01-17 00:14:18
合計ジャッジ時間 22,559 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 44
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (123 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (l, k) = (c[0], c[1]);
        var s = ReadLine();
        var t = ReadLine();
        var a = NList;
        var mod = 998_244_353;
        var rev = Exp(a.Sum(), mod - 2, mod);
        var dp = new long[l][];
        for (var i = 0; i < dp.Length; ++i) dp[i] = new long[l * 2 - 1];
        dp[0][l - 1] = 1;
        var nana = 0L;
        var minsa = 0L;
        for (var z = 0; z < k; ++z)
        {
            var ndp = new long[l][];
            for (var i = 0; i < ndp.Length; ++i) ndp[i] = new long[l * 2 - 1];
            for (var i = 0; i < dp.Length; ++i)
            {
                for (var j = 0; j < dp[i].Length; ++j)
                {
                    var si = s[i];
                    var ti = t[(i + j + 1) % l];
                    if (si == ti) ndp[(i + 1) % l][j] = (ndp[(i + 1) % l][j] + dp[i][j]) % mod;
                    else
                    {
                        var ps = a[si - 'a'] * rev % mod;
                        var pt = a[ti - 'a'] * rev % mod;
                        if (j + 1 >= dp[i].Length) nana = (nana + dp[i][j] * ps % mod) % mod;
                        else ndp[(i + 1) % l][j + 1] = (ndp[(i + 1) % l][j + 1] + dp[i][j] * ps % mod) % mod;
                        if (j == 0) minsa = (minsa + dp[i][j] * pt % mod) % mod;
                        else ndp[i][j - 1] = (ndp[i][j - 1] + dp[i][j] * pt % mod) % mod;
                        ndp[i][j] = (ndp[i][j] + dp[i][j] * ((1 - ps - pt + mod + mod) % mod) % mod) % mod;
                    }
                }
            }
            dp = ndp;
        }
        WriteLine($"{nana} {minsa}");
    }
    static long Exp(long n, long p, int mod)
    {
        long _n = n % mod;
        var _p = p;
        var result = 1L;
        if ((_p & 1) == 1) result *= _n;
        while (_p > 0)
        {
            _n = _n * _n % mod;
            _p >>= 1;
            if ((_p & 1) == 1) result = result * _n % mod;
        }
        return result;
    }
}
0