結果

問題 No.1136 Four Points Tour
ユーザー eSeFeSeF
提出日時 2021-02-04 20:38:51
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 15,966 bytes
コンパイル時間 1,200 ms
コンパイル使用メモリ 118,900 KB
実行使用メモリ 17,920 KB
最終ジャッジ日時 2024-07-01 01:58:29
合計ジャッジ時間 3,449 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
17,792 KB
testcase_01 AC 24 ms
17,664 KB
testcase_02 AC 24 ms
17,920 KB
testcase_03 AC 24 ms
17,536 KB
testcase_04 AC 23 ms
17,536 KB
testcase_05 AC 24 ms
17,664 KB
testcase_06 AC 24 ms
17,536 KB
testcase_07 AC 24 ms
17,664 KB
testcase_08 AC 24 ms
17,792 KB
testcase_09 AC 24 ms
17,664 KB
testcase_10 AC 24 ms
17,664 KB
testcase_11 AC 25 ms
17,792 KB
testcase_12 AC 24 ms
17,536 KB
testcase_13 AC 24 ms
17,408 KB
testcase_14 AC 24 ms
17,536 KB
testcase_15 AC 24 ms
17,536 KB
testcase_16 AC 24 ms
17,664 KB
testcase_17 AC 24 ms
17,536 KB
testcase_18 AC 25 ms
17,664 KB
testcase_19 AC 24 ms
17,792 KB
testcase_20 AC 24 ms
17,792 KB
testcase_21 AC 25 ms
17,536 KB
01_Sample03_evil.txt AC 24 ms
17,408 KB
04_Rnd_large_evil1.txt AC 24 ms
17,664 KB
04_Rnd_large_evil2.txt AC 24 ms
17,408 KB
04_Rnd_large_evil3.txt AC 24 ms
17,792 KB
04_Rnd_large_evil4.txt AC 24 ms
17,792 KB
04_Rnd_large_evil5.txt AC 24 ms
17,536 KB
04_Rnd_large_evil6.txt AC 25 ms
17,664 KB
04_Rnd_large_evil7.txt AC 24 ms
17,664 KB
04_Rnd_large_evil8.txt AC 24 ms
17,536 KB
04_Rnd_large_evil9.txt AC 24 ms
17,536 KB
04_Rnd_large_evil10.txt AC 23 ms
17,792 KB
05_Rnd_huge_evil1.txt AC 24 ms
17,664 KB
05_Rnd_huge_evil2.txt AC 24 ms
17,664 KB
05_Rnd_huge_evil3.txt AC 25 ms
17,280 KB
05_Rnd_huge_evil4.txt AC 24 ms
17,664 KB
05_Rnd_huge_evil5.txt AC 24 ms
17,664 KB
05_Rnd_huge_evil6.txt AC 25 ms
17,792 KB
05_Rnd_huge_evil7.txt AC 24 ms
17,536 KB
99_evil_01.txt AC 24 ms
17,664 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using ModInt = AtCoder_MOD.ModInt<AtCoder_MOD.Mod1000000007>;using static AtCoder_MOD.ModCalc<AtCoder_MOD.Mod1000000007>;
//using ModInt = AtCoder_MOD.ModInt<AtCoder_MOD.Mod998244353>;using static AtCoder_MOD.ModCalc<AtCoder_MOD.Mod998244353>;
namespace AtCoder_Main
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw);

            int Testcase = 1;
            //Testcase = int.Parse(Console.ReadLine());
            while (Testcase-- > 0) Solve();

            Console.Out.Flush();
        }
        static void Solve()
        {
            long N = long.Parse(Console.ReadLine());
            var dp = new ModInt[4];
            dp[0] = 1;
            var a = new AtCoder_MOD.MOD_Matrix<AtCoder_MOD.Mod1000000007>(4);
            for(var i = 0; i < 4; i++)
            {
                for(var j = 0; j < 4; j++)
                {
                    a[i][j] = i == j ? 0 : 1;
                }
            }
            a = a.Pow(a, N);
            dp = a * dp;
            Console.WriteLine(dp[0]);
        }
        
    }
}
namespace AtCoder_MOD
{
    public interface IMod
    {
        int Mod { get; }
        // isprime ?
    }
    public interface INTTFriendly
    {
        int primitive_root { get; }
    }
    public readonly struct Mod1000000007 : IMod
    {
        public int Mod => 1000000007;
    }
    public readonly struct Mod998244353 : IMod, INTTFriendly
    {
        public int Mod => 998244353;
        public int primitive_root => 3;
    }
    public struct ModInt<T> where T : IMod
    {
        private int value;
        // 0 <= x < mod 以外でも OK
        public ModInt(int x)
        {
            if (x < 0 || x >= default(T).Mod) x %= default(T).Mod;
            if (x < 0) x += default(T).Mod;
            value = x;
        }
        public ModInt(long x)
        {
            if (x < 0 || x >= default(T).Mod) x %= default(T).Mod;
            if (x < 0) x += default(T).Mod;
            value = (int)x;
        }
        // 0 <= x < mod
        public ModInt(uint x) => value = (int)x;

        public static ModInt<T> operator +(ModInt<T> a, ModInt<T> b)
        {
            var nv = a.value + b.value;
            if (nv >= default(T).Mod) nv -= default(T).Mod;
            return new ModInt<T>((uint)nv);
        }
        public static ModInt<T> operator ++(ModInt<T> a) => a + 1;

        public static ModInt<T> operator -(ModInt<T> a, ModInt<T> b)
        {
            var nv = a.value - b.value;
            if (nv < 0) nv += default(T).Mod;
            return new ModInt<T>((uint)nv);
        }
        public static ModInt<T> operator --(ModInt<T> a) => a - 1;


        public static ModInt<T> operator *(ModInt<T> a, ModInt<T> b) => new ModInt<T>((uint)(((long)a.value * b.value) % default(T).Mod));
        //符号
        public static ModInt<T> operator +(ModInt<T> a) => a;
        public static ModInt<T> operator -(ModInt<T> a) => a.value == 0 ? a : new ModInt<T>((uint)(default(T).Mod - a.value));
        public ModInt<T> Pow(long n)
        {
            if (n < 0) return Pow(-n).Pow(default(T).Mod - 2);
            var p = this;
            var ret = new ModInt<T>(1u);
            while (n > 0)
            {
                if ((n & 1) != 0) ret *= p;
                p *= p;
                n >>= 1;
            }
            return ret;
        }
        public ModInt<T> Inverse()
        {
            Debug.Assert(value != 0);
            int x, u, s, t, k;
            x = 1; u = 0;
            t = default(T).Mod;
            s = value;
            while (t > 0)
            {
                k = s / t;
                s -= k * t;
                (s, t) = (t, s);
                x -= k * u;
                (x, u) = (u, x);
            }
            return new ModInt<T>((uint)(x < 0 ? x + default(T).Mod : x));
        }

        public static ModInt<T> operator /(ModInt<T> a, ModInt<T> b) => (a * b.Inverse());
        public static bool operator ==(ModInt<T> a, ModInt<T> b) => a.value == b.value;
        public static bool operator !=(ModInt<T> a, ModInt<T> b) => a.value != b.value;
        public override bool Equals(object obj) => obj is ModInt<T> && this == (ModInt<T>)obj;
        public override int GetHashCode() => value.GetHashCode();
        public override string ToString() => value.ToString();


        //キャスト
        public static implicit operator ModInt<T>(int n) => new ModInt<T>(n);
        public static implicit operator ModInt<T>(long n) => new ModInt<T>(n);
        public static explicit operator int(ModInt<T> a) => a.value;
        public static explicit operator long(ModInt<T> a) => a.value;

        public static int GetMod() => default(T).Mod;
    }
    public static class ModCalc<T> where T : IMod
    {
        static readonly List<ModInt<T>> fac = new List<ModInt<T>>() { 1 };
        static List<ModInt<T>> facinv;
        static int MAX_N;
        // Do Use Init(Max_n) Before using other functions
        public static void Init_Mod(int n)
        {
            MAX_N = n;
            for (int i = 1; i <= n; i++) fac.Add(fac.Last() * i);
            facinv = new List<ModInt<T>>() { fac[n].Inverse() };
            for (int i = n; i > 0; i--) facinv.Add(facinv.Last() * i);
            facinv.Reverse();
        }
        public static void Reset()
        {
            MAX_N = -1;
            fac.Clear();
            facinv.Clear();
        }
        public static ModInt<T> Fac(int n)
        {
            Debug.Assert(n <= MAX_N);
            return fac[n];
        }
        public static ModInt<T> Finv(int n)
        {
            Debug.Assert(n <= MAX_N);
            return facinv[n];
        }
        public static ModInt<T> Comb(int n, int r)
        {
            Debug.Assert(n <= MAX_N);
            if (n < 0 || r < 0 || n < r) return 0;
            return fac[n] * facinv[n - r] * facinv[r];
        }
        public static ModInt<T> ModPow(long x, long n) => new ModInt<T>(x).Pow(n);
        public static ModInt<T> ModPow(int x, long n) => new ModInt<T>((uint)x).Pow(n);
        public static ModInt<T> ModPow(ModInt<T> x, long n) => x.Pow(n);
        public static ModInt<T> Inv(long x) => new ModInt<T>(x).Inverse();
        public static ModInt<T> Inv(int x) => new ModInt<T>((uint)x).Inverse();

        public static List<ModInt<T>> GetFac() => fac;
        public static List<ModInt<T>> GetFacInv() => facinv;
    }

    public struct MOD_Matrix<T> where T : IMod
    {
        int n;
        ModInt<T>[][] mat;
        public MOD_Matrix(int size)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
        }
        public MOD_Matrix(int size, ModInt<T>[,] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];
        }
        public MOD_Matrix(int size, ModInt<T>[][] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];
        }
        public MOD_Matrix(int size, long[,] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];
        }
        public MOD_Matrix(int size, long[][] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];
        }
        public MOD_Matrix(int size, int[,] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];
        }
        public MOD_Matrix(int size, int[][] A)
        {
            n = size;
            mat = new ModInt<T>[n][];
            for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];
            for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];
        }
        public ModInt<T>[] this[int id]
        {
            set
            {
                Debug.Assert(0 <= id && id < n);
                mat[id] = value;
            }
            get
            {
                Debug.Assert(0 <= id && id < n);
                return mat[id];
            }
        }
        public ModInt<T> this[int id1, int id2]
        {
            set
            {
                Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n);
                mat[id1][id2] = value;
            }
            get
            {
                Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n);
                return mat[id1][id2];
            }
        }


        public static MOD_Matrix<T> operator +(MOD_Matrix<T> A, MOD_Matrix<T> B)
        {
            Debug.Assert(A.n == B.n);
            for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] += B[i][j];
            return A;
        }
        public static MOD_Matrix<T> operator -(MOD_Matrix<T> A, MOD_Matrix<T> B)
        {
            Debug.Assert(A.n == B.n);
            for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] -= B[i][j];
            return A;
        }
        public static MOD_Matrix<T> operator *(MOD_Matrix<T> A, MOD_Matrix<T> B)
        {
            Debug.Assert(A.n == B.n);
            var ret = new MOD_Matrix<T>(A.n);
            for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++)
                {
                    for (var k = 0; k < A.n; k++) ret[i][j] += A[i][k] * B[k][j];
                }
            return ret;
        }
        public static ModInt<T>[] operator *(MOD_Matrix<T> A, ModInt<T>[] V)
        {
            Debug.Assert(A.n == V.Length);
            var ret = new ModInt<T>[A.n];
            for(var i = 0; i < A.n; i++)
            {
                for (var j = 0; j < A.n; j++) ret[i] += A[i][j] * V[j];
            }
            return ret;
        }

        public static MOD_Matrix<T> operator *(MOD_Matrix<T> A, ModInt<T> k)
        {
            for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] *= k;
            return A;
        }

        public MOD_Matrix<T> Pow(MOD_Matrix<T> A, long K)
        {
            var ret = new MOD_Matrix<T>(A.n);
            var P = A;
            for (var i = 0; i < A.n; i++) ret[i][i] = 1;
            while (K > 0)
            {
                if ((K & 1) != 0) ret *= P;
                P *= P;K >>= 1;
            }
            return ret;
        }

    }

    public class MOD_NTT<T> where T : IMod, INTTFriendly
    {
        private readonly int mod;
        private readonly int root;
        public MOD_NTT()
        {
            mod = default(T).Mod;
            root = default(T).primitive_root;
        }
        void NTT(ref ModInt<T>[] a, bool rev = false)
        {
            var n = a.Length;
            if (n == 1) return;
            var b = new ModInt<T>[n];
            var s = new ModInt<T>(root).Pow(rev ? mod - 1 - (mod - 1) / n : (mod - 1) / n);
            var kp = new List<ModInt<T>>() { 1 };
            int i, j, k, l, r;
            for (i = 0; i < (n >> 1); ++i) kp.Add(kp.Last() * s);
            for (i = 1, l = (n >> 1); i < n; i <<= 1, l >>= 1)
            {
                for (j = 0, r = 0; j < l; ++j, r += i)
                {
                    for (k = 0, s = kp[i * j]; k < i; ++k)
                    {
                        var p = a[k + r]; var q = a[k + r + n / 2];
                        b[k + 2 * r] = (p + q);
                        b[k + 2 * r + i] = ((p - q) * s);
                    }
                }
                (a, b) = (b, a);
            }
            if (rev)
            {
                s = new ModInt<T>(n).Inverse();
                for (i = 0; i < n; ++i) a[i] *= s;
            }
        }
        public ModInt<T>[] Convolution_MOD(ModInt<T>[] a, ModInt<T>[] b)
        {
            int N = a.Length + b.Length - 1;
            int t = 1;
            while (t < N) t <<= 1;
            var nxa = new ModInt<T>[t];
            var nxb = new ModInt<T>[t];
            for (var i = 0; i < a.Length; ++i) nxa[i] = a[i];
            for (var i = 0; i < b.Length; ++i) nxb[i] = b[i];
            NTT(ref nxa);
            NTT(ref nxb);
            for (var i = 0; i < t; i++) nxa[i] *= nxb[i];
            NTT(ref nxa, true);
            return nxa[0..N];
        }
        public ModInt<T>[] Convolution_MOD(long[] a, long[] b)
        {
            int N = a.Length + b.Length - 1;
            int t = 1;
            while (t < N) t <<= 1;
            var nxa = new ModInt<T>[t];
            var nxb = new ModInt<T>[t];
            for (var i = 0; i < a.Length; ++i) nxa[i] = a[i];
            for (var i = 0; i < b.Length; ++i) nxb[i] = b[i];
            NTT(ref nxa);
            NTT(ref nxb);
            for (var i = 0; i < t; i++) nxa[i] *= nxb[i];
            NTT(ref nxa, true);
            return nxa[0..N];
        }
    }
    //次数固定、NTT対応modのみ
    public struct FormalPowerSeries<T> where T : IMod, INTTFriendly
    {
        int n;
        ModInt<T>[] P;
        static readonly MOD_NTT<T> C = new MOD_NTT<T>();

        public FormalPowerSeries(int n)
        {
            this.n = n;
            P = new ModInt<T>[n + 1];
        }
        public int Length => n;
        public ModInt<T> this[int id]
        {
            set
            {
                Debug.Assert(0 <= id && id <= n);
                P[id] = value;
            }
            get
            {
                Debug.Assert(0 <= id && id <= n);
                return P[id];
            }
        }
        //Add
        //O(min(n,m))
        public static FormalPowerSeries<T> operator +(FormalPowerSeries<T> F, FormalPowerSeries<T> G)
        {
            int m = Math.Min(F.Length, G.Length);
            for (var i = 0; i <= m; i++) F[i] += G[i];
            return F;
        }
        //O(1)
        public static FormalPowerSeries<T> operator +(FormalPowerSeries<T> F, ModInt<T> a)
        {
            F[0] += a;
            return F;
        }

        //Subtract
        //O(min(n,m))
        public static FormalPowerSeries<T> operator -(FormalPowerSeries<T> F, FormalPowerSeries<T> G)
        {
            int m = Math.Min(F.Length, G.Length);
            for (var i = 0; i <= m; i++) F[i] -= G[i];
            return F;
        }
        //O(1)
        public static FormalPowerSeries<T> operator -(FormalPowerSeries<T> F, ModInt<T> a)
        {
            F[0] -= a;
            return F;
        }
        // Multiply
        //O(nlog(n))
        //下位 n 項のみ残すことに注意
        public static FormalPowerSeries<T> operator *(FormalPowerSeries<T> F, FormalPowerSeries<T> G)
        {
            F.P = C.Convolution_MOD(F.P, G.P)[0..(F.n + 1)];
            return F;
        }
        //O(n)
        public static FormalPowerSeries<T> operator *(FormalPowerSeries<T> F, ModInt<T> a)
        {
            for (var i = 0; i <= F.n; i++) F[i] *= a;
            return F;
        }

        //Divide
        //Todo F/=G
        //O(n+log(mod))
        public static FormalPowerSeries<T> operator /(FormalPowerSeries<T> F, ModInt<T> a)
        {
            var inv = a.Inverse();
            for (var i = 0; i <= F.n; i++) F[i] *= inv;
            return F;
        }
    }
}
0