SRM509 Div1Easy LuckyRemainder

http://community.topcoder.com/stat?c=problem_statement&pm=11138

二項係数を扱うのは難しいねって話

$n\times 10^k\equiv n\times 1^k\equiv n\pmod 9$ なので、生成される数字に、1-9がそれぞれいくつ含まれているかを考えればいい。ということで後は数え上げるだけなのだが、ここでやらかす。結果を言うと、二項係数mod9が求められなかった。

文字列のサイズを $N$ とすると、左から $i$ (0-indexed)番目の数が現れる回数は、

$\displaystyle \sum_{j=0}^{N-1}\sum_{k=0}^{N-1}{}_i \mathrm{C} _{k-j}\times {}_{N-i-1} \mathrm{C} _j$

で表される。（説明略）そのため、手元の二項係数ライブラリ（適当にコピペしただけ）を貼ってmod9を取った（コード1）のだが、サンプルから全く合わない。色々確認すると、二項係数の計算がどうも怪しい。調べると、自分のライブラリはmod素数でないといけないことが判明した。結局、DPで二項係数のテーブルを作成するライブラリ（これもコピペだけど）を使って通した。（コード2）
他人のライブラリをよく理解せずに使ってはいけない（戒め）
drken1215.hatenablog.com
コード1のライブラリをここから引っぱった記憶がないのですが、変数名等全く一緒なので絶対参考にしたのだと思います。コード2については確実にここから引っ張りました。ありがとうございます。

コード1（これはX="9999929999999999999999999999999999999999"で落とされる）

#include <bits/stdc++.h>
using namespace std;
const int MAX=510000;
const int MOD=1000000007;
//階乗,逆元,逆元の階乗
long long fac[MAX],finv[MAX],inv[MAX];

class LuckyRemainder {
public:
    //テーブルを作る前処理
    void COMinit() {
        fac[0]=fac[1]=1;
        finv[0]=finv[1]=1;
        inv[1]=1;
        for (int i=2;i<MAX;i++){
            fac[i]=fac[i-1]*i%MOD;
            inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
            finv[i]=finv[i-1]*inv[i]%MOD;
        }
    }

    //二項係数計算
    long long COM(int n,int k){
        if (n<k) return 0;
        if (n<0||k<0) return 0;
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
    }

    int getLuckyRemainder( string X ) {
        //前処理
        COMinit();
        int n=X.size();
        long long ans=0;
        // 位置
        for(int i=0;i<n;i++){
            long long num=X[i]-'0';
            // num*10^jの出現回数
            for(int j=0;j<n;j++){
                // 桁数
                for(int k=0;k<n;k++){
                    ans+=num*(COM(i,k-j)%9)*(COM(n-i-1,j)%9);
                    ans%=9;
                }
            }
        }
        return ans;
    }
};

コード2

#include <bits/stdc++.h>
using namespace std;
const int MAX_C=1000;
const int MOD=9;

long long Com[MAX_C][MAX_C];

class LuckyRemainder {
public:
    void calc_com() {
        memset(Com, 0, sizeof(Com));
        Com[0][0] = 1;
        for (int i = 1; i < MAX_C; ++i) {
            Com[i][0] = 1;
            for (int j = 1; j < MAX_C; ++j) {
                Com[i][j] = (Com[i-1][j-1] + Com[i-1][j]) % MOD;
            }
        }
    }

    int getLuckyRemainder( string X ) {
        //前処理
        calc_com();
        int n=X.size();
        long long ans=0;
        // 位置
        for(int i=0;i<n;i++){
            long long num=X[i]-'0';
            // num*10^jの出現回数
            for(int j=0;j<n;j++){
                // 桁数
                for(int k=0;k<n;k++){
                    if(k-j>=0&&n-i-1>=0) ans+=num*Com[i][k-j]*Com[n-i-1][j];
                    ans%=MOD;
                }
            }
        }
        return ans;
    }
};