結果

問題 No.117 組み合わせの数
ユーザー 明智重蔵明智重蔵
提出日時 2015-08-23 17:26:05
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 5,668 bytes
コンパイル時間 3,081 ms
コンパイル使用メモリ 112,872 KB
実行使用メモリ 63,312 KB
最終ジャッジ日時 2024-07-18 12:52:28
合計ジャッジ時間 15,532 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Text.RegularExpressions;

class Program
{
    const int DeviVal = 1000000000 + 7;

    static string InputPattern = "Input3";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("C(4,2)");
            WillReturn.Add("C(5,1)");
            WillReturn.Add("P(3,2)");
            WillReturn.Add("P(10,10)");
            WillReturn.Add("H(3,2)");
            //6
            //5
            //6
            //3628800
            //6
            //条件を満たす組み合わせの数は：
            //1番目のクエリは、{1,2},{1,3},{1,4},{2,3},{2,4},{3,4} の6通り
            //2番目のクエリは、{1},{2},{3},{4},{5} の5通り
            //3番目のクエリは、(1,2),(1,3),(2,1),(2,3),(3,1),(3,2) の6通り
            //4番目のクエリは、1から10までを並び替える場合の数と等しいので10!通り
            //5番目のクエリは、{1,1},{1,2},{1,3},{2,2},{2,3},{3,3} の6通り
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("C(1,1000000)");
            WillReturn.Add("C(0,0)");
            WillReturn.Add("P(1000000,1000000)");
            WillReturn.Add("P(1,10)");
            WillReturn.Add("H(1,1000)");
            //0
            //1
            //641102369
            //0
            //1
            //1番目のクエリは、10の6乗個の異なる整数を選ぶことは不可能なので，答えは0
            //2番目のクエリは、0個の整数を選ぶ方法の数は，何も選ばないという1通り
            //3番目のクエリは、答えは mod(10の9乗 +7)で出力することを忘れないで下さい
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        Eratosthenes();

        List<string> InputList = GetInputList();
        foreach (string EachLine in InputList.Skip(1)) {
            Match InsMatch =
                Regex.Match(EachLine, @"^([CPH])\(([0-9]+),([0-9]+)\)$");
            string Cap1 = InsMatch.Groups[1].Value;
            string Cap2 = InsMatch.Groups[2].Value;
            string Cap3 = InsMatch.Groups[3].Value;

            long Result = 0;
            int Param1 = int.Parse(Cap2);
            int Param2 = int.Parse(Cap3);
            if (Cap1 == "C") Result = CalcC(Param1, Param2);
            if (Cap1 == "P") Result = CalcP(Param1, Param2);
            if (Cap1 == "H") Result = CalcH(Param1, Param2);

            //Console.WriteLine("{0}{1}{2}={2}", Param1, Cap1, Param2, Result);
            Console.WriteLine(Result);
        }
    }

    const int Jyougen = 1000000;
    static int[] SosuuArr;

    //エラトステネスの篩
    static void Eratosthenes()
    {
        var CheckArr = new System.Collections.BitArray(Jyougen + 1);
        for (int I = 2; I <= CheckArr.Count - 1; I++) {
            CheckArr[I] = true;
        }
        for (int I = 2; I <= CheckArr.Count - 1; I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (CheckArr[I]) {
                for (int J = I * 2; J <= CheckArr.Count - 1; J += I) {
                    CheckArr[J] = false;
                }
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= CheckArr.Count - 1; I++)
            if (CheckArr[I]) SosuuList.Add(I);

        SosuuArr = SosuuList.ToArray();
    }

    //素因数分解した素因数の配列を返す
    static int[] DeriveSoinsuuArr(int pTarget)
    {
        if (Array.BinarySearch<int>(SosuuArr, pTarget) >= 0) {
            return new int[] { pTarget };
        }

        var SoinsuuList = new List<int>();
        for (int I = 0; I <= SosuuArr.GetUpperBound(0); I++) {
            while (pTarget % SosuuArr[I] == 0) {
                SoinsuuList.Add(SosuuArr[I]);
                pTarget /= SosuuArr[I];
            }
            if (pTarget == 1) break;
        }
        return SoinsuuList.ToArray();
    }

    //nPkを計算
    static long CalcP(int pN, int pK)
    {
        if (pN == 0) return 1;
        if (pN < pK) return 0;

        long WillReturn = 1;
        for (int I = pN; I >= pN - pK + 1; I--) {
            WillReturn = (WillReturn * I) % DeviVal;
        }
        return WillReturn;
    }

    //nCkを計算
    static long CalcC(int pN, int pK)
    {
        if (pN == 0) return 1;
        if (pN < pK) return 0;

        pK = Math.Min(pK, pN - pK);

        var ProdList = new List<int>();
        var DeviList = new List<int>();

        for (int I = pN; I >= pN - pK + 1; I--) {
            ProdList.Add(I);
        }
        for (int I = 1; I <= pK; I++) {
            DeviList.AddRange(DeriveSoinsuuArr(I));
        }

        //分母を全てはらってから、総積をDeviValで割った余りを求める
        for (int I = DeviList.Count - 1; 0 <= I; I--) {
            for (int J = 0; J <= ProdList.Count - 1; J++) {
                if (ProdList[J] % DeviList[I] == 0) {
                    ProdList[J] /= DeviList[I];
                    DeviList.RemoveAt(I);
                    break;
                }
            }
        }
        long WillReturn = 1;
        ProdList.ForEach(X => WillReturn = (WillReturn * X) % DeviVal);
        return WillReturn;
    }

    //nHkを計算
    static long CalcH(int pN, int pK)
    {
        return CalcC(pN + pK - 1, pK);
    }
}
0