SRM467 Div1 Medium(500) SuperSum - kusano

オンライン整数列大辞典に訊いたところ、_n+kC_k+1だった。
Javaを覚えるか、多倍長整数のライブラリを準備しておくかしないと、この手の問題を戦えない……。

追記：
法が素数の場合は除算もできるらしい。知らなかった。

#include <vector>

using namespace std;

class SuperSum
{
    int comb( int n, int k );
public:
    int calculate( int k, int n );
};

int SuperSum::calculate( int k, int n )
{
    return comb(n+k,k+1);
}

int SuperSum::comb( int n, int k )
{
    //  n*(n-1)*……*(n-k+1)
    vector<int> num;
    for ( int i=0; i<k; i++ )
        num.push_back( n - i );

    //  /k!
    for ( int i=1; i<=k; i++ )
    {
        int t = i;
        int c = 2;

        while ( t > 1 )
        {
            if ( t % c == 0 )
            {
                t /= c;

                for ( int j=0; j<k; j++ )
                    if ( num[j] % c == 0 )
                    {
                        num[j] /= c;
                        break;
                    }
            }
            else
                c++;
        }
    }

    int ans = 1;
    for ( int i=0; i<k; i++ )
        ans = (int)( (long long)ans * num[i] % 1000000007 );

    return ans;
}