Submission #5025538
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007; ll modpow(ll x, ll n) { ll res = 1; while (n > 0) { if (n & 1) res = res * x % MOD; x = x * x % MOD; n >>= 1; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); int a; ll b, c; cin >> a >> b >> c; ll num = min((ll)a, c) - 1; ll inv = 1; for (int i = 1; i <= num; i++) { (inv *= i) %= MOD; } inv = modpow(inv, MOD - 2); ll hoge = 1; for (int i = 1; i <= num; i++) { (hoge *= (c - i)) %= MOD; } vector<ll> memo(a, 1); for (int i = 1; i < a; i++) { memo[i] = memo[i - 1] * b % MOD; } ll ans = 0; ll maxv = c - 1, minv = c - num; for (int i = a - 1; i >= 0; i--) { (ans += memo[i] * hoge % MOD * inv % MOD) %= MOD; maxv++; hoge = hoge * maxv % MOD * modpow(minv, MOD - 2) % MOD; minv++; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Range Sum Queries |
User | fine |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1087 Byte |
Status | WA |
Exec Time | 19 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 12 | 0 / 48 | 0 / 40 | ||||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
Subtask1 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt |
Subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt, sub2_9.txt |
Subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt, sub2_9.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub3_7.txt, sub3_8.txt, sub3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | WA | 1 ms | 256 KB |
sub1_1.txt | AC | 1 ms | 256 KB |
sub1_2.txt | AC | 1 ms | 256 KB |
sub1_3.txt | WA | 1 ms | 256 KB |
sub1_4.txt | AC | 1 ms | 256 KB |
sub1_5.txt | WA | 1 ms | 256 KB |
sub1_6.txt | WA | 1 ms | 256 KB |
sub1_7.txt | AC | 1 ms | 256 KB |
sub1_8.txt | AC | 1 ms | 256 KB |
sub1_9.txt | AC | 1 ms | 256 KB |
sub2_1.txt | WA | 11 ms | 640 KB |
sub2_2.txt | WA | 6 ms | 512 KB |
sub2_3.txt | WA | 11 ms | 640 KB |
sub2_4.txt | AC | 15 ms | 896 KB |
sub2_5.txt | AC | 13 ms | 768 KB |
sub2_6.txt | WA | 6 ms | 512 KB |
sub2_7.txt | AC | 19 ms | 1024 KB |
sub2_8.txt | WA | 3 ms | 384 KB |
sub2_9.txt | WA | 2 ms | 256 KB |
sub3_1.txt | WA | 15 ms | 896 KB |
sub3_2.txt | WA | 1 ms | 256 KB |
sub3_3.txt | WA | 10 ms | 640 KB |
sub3_4.txt | WA | 13 ms | 768 KB |
sub3_5.txt | WA | 13 ms | 768 KB |
sub3_6.txt | WA | 19 ms | 1024 KB |
sub3_7.txt | WA | 2 ms | 256 KB |
sub3_8.txt | WA | 18 ms | 1024 KB |
sub3_9.txt | WA | 19 ms | 1024 KB |