結果

問題 No.117 組み合わせの数
ユーザー threecoursethreecourse
提出日時 2018-05-25 02:14:00
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,704 ms / 5,000 ms
コード長 4,025 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 113,340 KB
実行使用メモリ 52,608 KB
最終ジャッジ日時 2024-06-28 17:50:44
合計ジャッジ時間 6,456 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,704 ms
52,608 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.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public long T;
        public FermatCombination comb;

        public void Run()
        {
            // C(N, K) -- Combination
            // P(N, K) -- Factrial
            // H(N, K) -- C(N+K-1, K) (n==k==0 -- corner case)

            comb = new FermatCombination(2000000);

            T = Input.ReadInt();
            for (int i = 0; i < T; i++)
            {
                string s = Console.ReadLine();
                string tp = s.Substring(0, 1);
                string tpl = s.Substring(2, s.Length - 3);
                int n = int.Parse(tpl.Split(',')[0]);
                int k = int.Parse(tpl.Split(',')[1]);

                long val;
                if (tp == "C")
                    val = C(n, k);
                else if (tp == "P")
                    val = P(n, k);
                else
                    val = H(n, k);
                Console.WriteLine(val);
            }

        }

        public long C(int n, int k)
        {
            if (n - k < 0) return 0;
            return comb.Combination(n, k);
        }

        public long P(int n, int k)
        {
            if (n - k < 0) return 0;
            return comb.Permutation(n, k);
        }

        public long H(int n, int k)
        {
            if (n == 0 && n == k) return 1;
            return C(n + k - 1, k);
        }
    }

    // libs ----------
    class FermatCombination
    {
        public long[] Factrial; // 階乗
        public long[] Inverse; // 逆元
        public long MOD = 1000000007;

        public FermatCombination(int n)
        {

            Factrial = new long[n + 1];
            Inverse = new long[n + 1];
            Factrial[0] = 1;
            Inverse[0] = 1;

            for (int i = 1; i <= n; i++)
            {
                Factrial[i] = (Factrial[i - 1] * i) % MOD;
            }

            for (int i = 1; i <= n; i++)
            {
                // フェルマーの小定理で逆元を求める
                Inverse[i] = Power(Factrial[i], (int)MOD - 2, MOD) % MOD;
            }
        }

        public long Permutation(int n, int k)
        {
            return Factrial[n] * Inverse[n - k] % MOD;
        }

        public long Combination(int n, int k)
        {
            return Factrial[n] * Inverse[k] % MOD * Inverse[n - k] % MOD;
        }

        public static long Power(long x, long n, long M)
        {
            long tmp = 1;

            if (n > 0)
            {
                tmp = Power(x, n / 2, M);
                if (n % 2 == 0) tmp = (tmp * tmp) % M;
                else tmp = (((tmp * tmp) % M) * x) % M;
            }

            return tmp;
        }
    }

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }

    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}
0