Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-10-03

TopCoder SRM467 Div1 Medium SuperSum

21:59 | TopCoder SRM467 Div1 Medium SuperSum - chokudaiの日記 を含むブックマーク はてなブックマーク - TopCoder SRM467 Div1 Medium SuperSum - chokudaiの日記 TopCoder SRM467 Div1 Medium SuperSum - chokudaiの日記 のブックマークコメント

問題

 f(0,n)=n

 f(k,n)=\sum^n_i f(k-1,i)

とするとき、f(k,n)を求めよ

kは50まで nは10億まで 答えはmod1000000007

回答

パスカルの三角形みたいになるので二項定理

割り算はいつも通りフェルマーの小定理のあれで

public class SuperSum {
    long mod = 1000000007;
    public int calculate(int k, int n)
    {
        return (int)(c(k + n, n - 1) % mod);
    }

    long c(int n, int k)
    {
        if (n / 2 < k) return c(n, n - k);
        int i;
        long res = 1;
        for (i = 0; i < k; i++)
        {
            res *= (n - i);
            res %= mod;
            // res /= (i + 1);
            res *= powmod(i + 1, mod - 2, mod);
            res %= mod;
        }
        return res % mod;
    }

    long powmod(long a, long n, long mod)
    {
        if (n == 0) return 1;
        if (n % 2 == 1) return a * powmod(a, n - 1, mod) % mod;
        long c = powmod(a, n / 2, mod);
        return c * c % mod;
    }
}

ちっちっ2010/10/08 17:08初期値0なら全部0じゃない?

chokudaichokudai2010/10/20 15:11おっと、ミスでした、ありがとうございまーす!

 |