結果

問題 No.2964 Obstruction Bingo
ユーザー kakel-san
提出日時 2025-01-17 01:20:06
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 397 ms / 2,468 ms
コード長 3,084 bytes
コンパイル時間 13,652 ms
コンパイル使用メモリ 170,712 KB
実行使用メモリ 208,448 KB
最終ジャッジ日時 2025-01-17 01:22:15
合計ジャッジ時間 28,299 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (291 ミリ秒)。
  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;
        WriteLine(Bingo(l, k, s, t, a));
    }
    static string Bingo(int l, int k, string s, string t, int[] a)
    {
        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 + l) % l];
                    if (si == ti)
                    {
                        var ps = a[si - 'a'] * rev % mod;
                        ndp[(i + 1) % l][j] = (ndp[(i + 1) % l][j] + dp[i][j] * ps % mod) % mod;
                        ndp[i][j] = (ndp[i][j] + dp[i][j] * ((1 - ps + mod) % mod) % mod) % 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;
        }
        return $"{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