#612981 (C#(csc)) No.891 隣接3項間の漸化式

提出ソース

結果

問題	No.891 隣接3項間の漸化式
ユーザー	eSeF
提出日時	2021-02-04 21:09:36
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	32 ms / 2,000 ms
コード長	16,625 bytes
コンパイル時間	1,359 ms
コンパイル使用メモリ	119,680 KB
実行使用メモリ	19,456 KB
最終ジャッジ日時	2024-07-01 02:37:46
合計ジャッジ時間	4,038 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	28 ms 19,328 KB
testcase_01	AC	29 ms 19,328 KB
testcase_02	AC	29 ms 19,200 KB
testcase_03	AC	29 ms 19,200 KB
testcase_04	AC	28 ms 19,328 KB
testcase_05	AC	32 ms 19,200 KB
testcase_06	AC	29 ms 19,328 KB
testcase_07	AC	30 ms 19,456 KB
testcase_08	AC	30 ms 19,200 KB
testcase_09	AC	29 ms 19,072 KB
testcase_10	AC	28 ms 19,072 KB
testcase_11	AC	29 ms 19,200 KB
testcase_12	AC	29 ms 19,200 KB
testcase_13	AC	29 ms 19,072 KB
testcase_14	AC	27 ms 18,944 KB
testcase_15	AC	28 ms 19,200 KB
testcase_16	AC	28 ms 19,200 KB
testcase_17	AC	28 ms 19,072 KB
testcase_18	AC	28 ms 19,200 KB
testcase_19	AC	29 ms 19,328 KB
testcase_20	AC	28 ms 19,200 KB
testcase_21	AC	27 ms 19,072 KB
testcase_22	AC	29 ms 19,072 KB
testcase_23	AC	28 ms 19,072 KB
testcase_24	AC	27 ms 19,072 KB
testcase_25	AC	29 ms 19,072 KB
testcase_26	AC	29 ms 19,200 KB
testcase_27	AC	29 ms 19,200 KB
testcase_28	AC	29 ms 19,072 KB
testcase_29	AC	28 ms 19,328 KB
testcase_30	AC	28 ms 19,072 KB
testcase_31	AC	29 ms 19,328 KB
testcase_32	AC	29 ms 19,200 KB
testcase_33	AC	29 ms 19,328 KB
testcase_34	AC	29 ms 19,072 KB
testcase_35	AC	28 ms 19,328 KB
testcase_36	AC	29 ms 19,200 KB
testcase_37	AC	30 ms 19,200 KB
testcase_38	AC	29 ms 19,328 KB
testcase_39	AC	28 ms 19,328 KB
testcase_40	AC	29 ms 18,944 KB
testcase_41	AC	29 ms 19,328 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

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 Mod_Matrix = AtCoder_MOD.MOD_Matrix<AtCoder_MOD.Mod1000000007>;
//using ModInt = AtCoder_MOD.ModInt<AtCoder_MOD.Mod998244353>;using static AtCoder_MOD.ModCalc<AtCoder_MOD.Mod998244353>;using Mod_Matrix = AtCoder_MOD.MOD_Matrix<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()
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = input[0], b = input[1];
            long n = input[2];
            var ans = Mod_Matrix.Solve_Linear_dp(n, new ModInt[] { a, b }, new ModInt[] { 1, 0 });
            Console.WriteLine(ans);
        }
        
    }
}
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(long K)
        {
            if (K == 0)
            {
                var E = new MOD_Matrix<T>(n);
                for (var i = 0; i < n; i++) E[i][i] = 1;
                return E;
            }
            var ret = new MOD_Matrix<T>(n);
            var P = this;
            for (var i = 0; i < n; i++) ret[i][i] = 1;
            while (K > 0)
            {
                if ((K & 1) != 0) ret *= P;
                P *= P;K >>= 1;
            }
            return ret;
        }

        public static ModInt<T> Solve_Linear_dp(long N, ModInt<T>[] coefs, ModInt<T>[] inits)
        {
            int K = coefs.Length;
            if (N < K) return inits[K - 1 - N];
            var A = new MOD_Matrix<T>(K);
            for (var i = 0; i < K; i++)
            {
                if (i == 0) for (var j = 0; j < K; j++) A[i][j] = coefs[j];
                else A[i][i - 1] = 1;
            }
            N -= K - 1;
            
            A = A.Pow(N);
            inits = A * inits;
            return inits[0];
        }
    }

    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;
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード