mayoko’s diary

プロコンとかいろいろ。

square869120Contest #2 F - Range Sum Queries

解法

なんか調べると
b^(a-1-i) に掛け算される係数は 1/i! * c*(c+1)*...*(c+i) になります。なのでそれを実装すれば OK です。

調べ方ですが, b^3 あたりの列を調べると, b^0 の項が 1, 4, 10, ... となっています。b^2 では b^0 の項は 1, 3, 6, 10, ... となっていますが, これは明らかに 1/2*c*(c+1) です。
b^3 の列の b^0 の項は, 1/2*c*(c+1) の公差の数列になっているので

 p_{k+1} = p_k + \frac{1}{2}(k+1)(k+2)

ですが, これの解は pk = 1/6 k(k+1)(k+2) です。同様に数学的帰納法で b^i の係数もわかるのではい。

const int MOD = 1e9+7;
const int MAXA = 100100;

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

ll B[MAXA], C[MAXA];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a;
    ll b, c;
    cin >> a >> b >> c;
    B[0] = C[0] = 1;
    for (int i = 1; i <= a; i++) {
        B[i] = B[i-1]*b%MOD;
        C[i] = C[i-1]*(c+i-1)%MOD;
        (C[i] *= mod_inverse(i, MOD)) %= MOD;
    }
    ll ans = 0;
    for (int i = 0; i < a; i++) {
        (ans += B[a-i-1]*C[i]%MOD) %= MOD;
    }
    cout << ans << endl;
    return 0;
}