No.117 組み合わせの数

実装が面倒だったんでライブラリを貼り付けた。が、コーナーケースと初期時の 2*maxN するべきところを maxN にして RE してしまった...。orz
nComP の実装は 559C - Gerald and Giant Chess - shifth’s blog で使ったやつ。

class CombinationNumber {
public:
    void solve(void) {
            const int Mod = (int)(1e+9)+7;
            const int maxN = (int)1e+6;

            // O(maxN)
            nCombP nCr(2*maxN,Mod); // nCr(n+k-1,k をやるので 2*maxN 確保
            auto &fact = nCr.fact_; // fact[n] = n!

            int T;
            cin>>T;
            REP(_, T)
            {
                char type, a,b,c;
                int n,k;
                cin>>type>>a>>n>>b>>k>>a;
                (void)a;
                (void)b;
                (void)c;
                switch (type)
                {
                  case 'C':
                    cout<<nCr(n,k)<<endl;
                    break;
                  case 'P':
                    cout<<(fact[k]*nCr(n,k))%Mod<<endl;
                    break;
                  case 'H':
                    // nHk = (n+k-1)Ck
                    // H(0,0) = C(-1,0) = 1 がコーナーケースなので対応
                    if (n==0 && k==0)
                        cout<<1<<endl;
                    else
                        cout<<nCr(n+k-1,k)<<endl;
                    break;
                  default:
                    assert(false);
                }
            }
    }
};