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) の公差の数列になっているので
ですが, これの解は 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; }