| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19900 |
2016-02-25T06:51:19 Z |
Qwaz |
순열 (kriii4_T) |
C++ |
|
341 ms |
5816 KB |
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007LL;
int times_mod(int a, int b) {
return ll(a) * ll(b) % mod;
}
// solves a*x + b*y = d = gcd(a, b)
// if d == 1, x is a modular inverse of a mod b
void extended_gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
if(a < 0) {extended_gcd(-a, b, d, x, y); x *= -1; return;}
if(b < 0) {extended_gcd(a, -b, d, x, y); y *= -1; return;}
x = 0, y = 1;
ll lx = 1, ly = 0, frac, tmp;
while(b)
{
frac = a / b;
tmp = a; a = b; b = tmp % b;
tmp = x; x = lx - frac * x; lx = tmp;
tmp = y; y = ly - frac * y; ly = tmp;
}
x = lx; y = ly; d = a;
}
// calculates x^-1 mod a
ll inv_mod(ll x, ll a)
{
ll res, y, d;
extended_gcd(x, a, d, res, y);
return ((res % a) + a) % a;
}
int fact[1048576];
int main() {
int N, K;
cin >> N >> K;
fact[0] = 1;
for (int i = 1; i <= N + 1; i++)
fact[i] = times_mod(fact[i - 1], i);
int sum = 0;
for (int k = K + 1; k <= N; k++) {
int to_add = times_mod(times_mod(fact[N + 1], inv_mod(k + 1, mod)), N + 1 - k);
sum = (sum + to_add) % mod;
}
cout << sum << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 5 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 9 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 10 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 11 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 12 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 13 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 14 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 15 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 16 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 17 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 18 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 19 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 20 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 21 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 22 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 23 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 24 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 25 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 26 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 27 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 28 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 29 |
Correct |
0 ms |
5816 KB |
Output is correct |
| 30 |
Correct |
0 ms |
5816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
5816 KB |
Output is correct |
| 2 |
Correct |
106 ms |
5816 KB |
Output is correct |
| 3 |
Correct |
41 ms |
5816 KB |
Output is correct |
| 4 |
Correct |
27 ms |
5816 KB |
Output is correct |
| 5 |
Correct |
39 ms |
5816 KB |
Output is correct |
| 6 |
Correct |
33 ms |
5816 KB |
Output is correct |
| 7 |
Correct |
248 ms |
5816 KB |
Output is correct |
| 8 |
Correct |
140 ms |
5816 KB |
Output is correct |
| 9 |
Correct |
48 ms |
5816 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5816 KB |
Output is correct |
| 11 |
Correct |
92 ms |
5816 KB |
Output is correct |
| 12 |
Correct |
9 ms |
5816 KB |
Output is correct |
| 13 |
Correct |
48 ms |
5816 KB |
Output is correct |
| 14 |
Correct |
217 ms |
5816 KB |
Output is correct |
| 15 |
Correct |
123 ms |
5816 KB |
Output is correct |
| 16 |
Correct |
188 ms |
5816 KB |
Output is correct |
| 17 |
Correct |
93 ms |
5816 KB |
Output is correct |
| 18 |
Correct |
84 ms |
5816 KB |
Output is correct |
| 19 |
Correct |
21 ms |
5816 KB |
Output is correct |
| 20 |
Correct |
114 ms |
5816 KB |
Output is correct |
| 21 |
Correct |
68 ms |
5816 KB |
Output is correct |
| 22 |
Correct |
186 ms |
5816 KB |
Output is correct |
| 23 |
Correct |
72 ms |
5816 KB |
Output is correct |
| 24 |
Correct |
30 ms |
5816 KB |
Output is correct |
| 25 |
Correct |
43 ms |
5816 KB |
Output is correct |
| 26 |
Correct |
126 ms |
5816 KB |
Output is correct |
| 27 |
Correct |
14 ms |
5816 KB |
Output is correct |
| 28 |
Correct |
10 ms |
5816 KB |
Output is correct |
| 29 |
Correct |
340 ms |
5816 KB |
Output is correct |
| 30 |
Correct |
341 ms |
5816 KB |
Output is correct |
