제출 #19900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19900		Qwaz	순열 (kriii4_T)	C++98	100 / 100	341 ms	5816 KiB

T

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92