結果

問題 No.506 限られたジャパリまん
コンテスト
ユーザー 👑 kakel-san
提出日時 2026-11-15 14:03:15
言語 C#
(.NET 10.0.403 + ACL)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 731 ms / 2,000 ms
+ 843µs
コード長 6,101 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,975 ms
コンパイル使用メモリ 171,792 KB
実行使用メモリ 52,224 KB
最終ジャッジ日時 2026-11-15 14:03:39
合計ジャッジ時間 19,526 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (205 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code

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

class Program
{
    static long NN => long.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NList;
        var (h, w, k, p) = (c[0] + 1, c[1] + 1, c[2], c[3]);
        var fr = SList(k);
        var map = new int[h, w];
        for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j) map[i, j] = -1;
        for (var i = 0; i < k; ++i)
        {
            var s = fr[i].Split();
            map[int.Parse(s[0]), int.Parse(s[1])] = i;
        }
        var bitmax = 1 << k;
        var ans = new HugeInt(6);
        var maxb = 0;
        for (var b = 0; b < bitmax; ++b)
        {
            if (Popcount(b) != p) continue;
            var dp = new HugeInt[h, w];
            for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j)
            {
                dp[i, j] = new HugeInt(6);
                if (i == 0 && j == 0) dp[i, j] = HugeInt.Sum(dp[i, j], 1);
                if (map[i, j] >= 0 && ((b >> map[i, j]) & 1) == 0) continue;
                if (i > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i - 1, j]);
                if (j > 0) dp[i, j] = HugeInt.Sum(dp[i, j], dp[i, j - 1]);
            }
            if (dp[h - 1, w - 1].IsLarge(ans))
            {
                ans = dp[h - 1, w - 1];
                maxb = b;
            }
        }
        WriteLine(HugeInt.Mod(ans, 1_000_000_007));
        for (var i = 0; i < k; ++i) if (((maxb >> i) & 1) == 1) WriteLine(fr[i].Split()[2]);
    }
    /// <summary>
    /// 10^27以上の大きい値どうしの計算をO(logN)で行う
    /// </summary>
    class HugeInt
    {
        static int div = 1 << 30;
        public List<int> Digits;
        public HugeInt(int length)
        {
            Digits = new List<int>(length);
            for (var i = 0; i < length; ++i) Digits.Add(0);
        }
        public bool IsLarge(HugeInt b)
        {
            for (var i = Digits.Count - 1; i >= 0; --i)
            {
                if (Digits[i] > b.Digits[i]) return true;
                if (Digits[i] < b.Digits[i]) return false;
            }
            return false;
        }
        public override string ToString()
        {
            var c = new List<char>(Digits.Count);
            var flg = false;
            for (var i = Digits.Count - 1; i >= 0; --i)
            {
                if (Digits[i] > 0) flg = true;
                if (flg) c.Add((char)(Digits[i] + '0'));
            }
            if (c.Count == 0) c.Add('0');
            return string.Concat(c);
        }
        public static HugeInt Sum(HugeInt a, int b)
        {
            var ans = new HugeInt(a.Digits.Count);
            var add = (long)b;
            for (var i = 0; i < a.Digits.Count; ++i)
            {
                var sum = a.Digits[i] + add;
                if (sum > div)
                {
                    ans.Digits[i] = (int)(sum - div);
                    add = 1;
                }
                else
                {
                    ans.Digits[i] = (int)sum;
                    add = 0;
                }
            }
            return ans;
        }
        // public static HugeInt Rem(HugeInt a, int b)
        // {
        //     var ans = new HugeInt(a.Digits.Count);
        //     for (var i = 0; i < a.Digits.Count; ++i) ans.Digits[i] = a.Digits[i];
        //     ans.Digits[0] -= b;
        //     for (var i = 0; i < ans.Digits.Count; ++i)
        //     {
        //         if (ans.Digits[i] < 0)
        //         {
        //             var d = ans.Digits[i] / 10;
        //             ans.Digits[i] += d * 10;
        //             if (ans.Digits[i] < 0)
        //             {
        //                 ++d;
        //                 ans.Digits[i] += 10;
        //             }
        //             ans.Digits[i + 1] -= d;
        //         }
        //     }
        //     return ans;
        // }
        public static HugeInt Sum(HugeInt a, HugeInt b)
        {
            var ans = new HugeInt(a.Digits.Count);
            var add = 0;
            for (var i = 0; i < a.Digits.Count; ++i)
            {
                var sum = (long)a.Digits[i] + b.Digits[i] + add;
                if (sum > div)
                {
                    ans.Digits[i] = (int)(sum - div);
                    add = 1;
                }
                else
                {
                    ans.Digits[i] = (int)sum;
                    add = 0;
                }
            }
            return ans;
        }
        public static HugeInt Div(HugeInt a, int d)
        {
            var ans = new HugeInt(a.Digits.Count);
            var rem = 0L;
            for (var i = a.Digits.Count - 1; i >= 0; --i)
            {
                rem = rem * div + a.Digits[i];
                ans.Digits[i] = (int)(rem / d);
                rem = rem % d;
            }
            return ans;
        }
        public static long Mod(HugeInt a, long m)
        {
            var ans = 0L;
            for (var i = a.Digits.Count - 1; i >= 0; --i)
            {
                ans = (ans * div + a.Digits[i]) % m;
            }
            return ans;
        }
    }
    static int Popcount(long n)
    {
        var c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555);
        c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333);
        c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f);
        c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff);
        c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff);
        c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff);
        return (int)c;
    }
}
0