結果

問題 No.823 Many Shifts Easy
ユーザー yoshnaryyoshnary
提出日時 2019-04-27 00:11:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 265 ms / 2,000 ms
コード長 2,784 bytes
コンパイル時間 758 ms
コンパイル使用メモリ 98,284 KB
実行使用メモリ 34,900 KB
最終ジャッジ日時 2024-11-25 08:49:47
合計ジャッジ時間 4,101 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 254 ms
34,772 KB
testcase_01 AC 259 ms
34,648 KB
testcase_02 AC 254 ms
34,772 KB
testcase_03 AC 257 ms
34,768 KB
testcase_04 AC 259 ms
34,644 KB
testcase_05 AC 260 ms
34,644 KB
testcase_06 AC 265 ms
34,772 KB
testcase_07 AC 253 ms
34,648 KB
testcase_08 AC 256 ms
34,776 KB
testcase_09 AC 254 ms
34,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
using ll = long long;

// Modint
struct Mint {
	static const ll mod = (ll)(1e9 + 7);
	ll val;

	Mint() { val = 0; }
	Mint(ll a) {
		val = a;
		verify_value();
	}

	void verify_value() {
		if (val >= mod) val %= mod;
		if (val < 0) val %= mod, val += mod;
	}

	Mint pow(ll p) const {
		Mint cur = Mint(val), ret = 1;
		while (p > 0) {
			if (p & 1) ret *= cur;
			cur *= cur;
			p >>= 1LL;
		}
		return ret;
	}
	Mint inv() const {
		if (val == 0) cerr << "CAUTION: inv() is called with 0." << endl;
		return pow(mod - 2);
	}

	Mint operator+() const { return *this; }
	Mint operator-() const { return Mint(mod - val); }

	Mint operator+=(const Mint &a) {
		val += a.val;
		if (val >= mod) val -= mod;
		return Mint(val);
	}
	Mint operator*=(const Mint &a) {
		val *= a.val;
		if (val >= mod) val %= mod;
		return Mint(val);
	}
	Mint operator-=(const Mint &a) { return *this += -a; }
	Mint operator/=(const Mint &a) { return *this *= a.inv(); }

	Mint operator++() { return *this += Mint(1); }
	Mint operator--() { return *this -= Mint(1); }
	Mint operator++(int) {
		Mint ret = *this;
		++(*this);
		return ret;
	}
	Mint operator--(int) {
		Mint ret = *this;
		--(*this);
		return ret;
	}

	operator ll() const { return val; }
};

Mint operator+(const Mint &a, const Mint &b) {
	ll ret = a.val + b.val;
	if (ret >= Mint::mod) ret -= Mint::mod;
	return Mint(ret);
}
Mint operator*(const Mint &a, const Mint &b) {
	ll ret = a.val * b.val;
	if (ret >= Mint::mod) ret %= Mint::mod;
	return Mint(ret);
}
Mint operator-(const Mint &a, const Mint &b) { return a + (-b); }
Mint operator/(const Mint &a, const Mint &b) { return a * b.inv(); }

ostream &operator<<(ostream &out, const Mint &a) { return out << a.val; }
istream &operator>>(istream &in, Mint &a) {
	in >> a.val;
	a.verify_value();
	return in;
}


// Combinatorics
constexpr int MAX_N = 2000003;
Mint fact[MAX_N], inv[MAX_N];

void init_fact() {
	fact[0] = inv[0] = 1;
	for (ll i = 1; i < MAX_N; i++) {
		fact[i] = fact[i - 1] * Mint(i);
		inv[i] = fact[i].inv();
	}
}

// aCb
Mint C(int a, int b) {
	if (a < b) return 0;
	Mint res = fact[a];
	res *= inv[b];
	res *= inv[a - b];
	return res;
}

// aPb
Mint P(int a, int b) {
	if (a < b) return 0;
	return fact[a] * inv[a - b];
}

// aHb
Mint H(int a, int b) {
	if (b == 0) return 1;
	return C(a + b - 1, b);
}

int main() {
	int N, K; cin >> N >> K;
	init_fact();
	Mint ans = 0;
	for (int i = 1; i <= N; i++) {
		ans += P(N - 1, K)*Mint(i);
		if (i < N) ans += P(N - 2, K - 2)*H(K - 1, 2)*Mint(i);
	}
	cout << ans << endl;
	return 0;
}
0