結果
| 問題 |
No.823 Many Shifts Easy
|
| コンテスト | |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-04-30 18:00:07 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 175 ms / 2,000 ms |
| コード長 | 4,983 bytes |
| コンパイル時間 | 4,004 ms |
| コンパイル使用メモリ | 77,884 KB |
| 実行使用メモリ | 42,724 KB |
| 最終ジャッジ日時 | 2024-12-30 15:54:23 |
| 合計ジャッジ時間 | 6,346 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
import java.io.*;
import java.util.Scanner;
public class Main_yukicoder823 {
private static Scanner sc;
private static Printer pr;
private static void solve() {
final int MOD = 1_000_000_007;
int n = sc.nextInt();
int k = sc.nextInt();
PC pc = new PC(n, MOD);
long inv2 = pc.pow(2, MOD - 2);
if (k == 1) {
pr.println((long)n * (n + 1) % MOD * inv2 % MOD * (n - 1) % MOD);
return;
}
long all = pc.P(n, k);
// pr.println(all);
// pr.println(pc.C(n, k) * pc.fact[k]);
long ans = 0;
for (int i = 1; i < n; i++) {
long tmp = pc.C(n - 2, k - 2) * pc.fact[k] % MOD * inv2;
tmp %= MOD;
tmp += pc.C(n - 2, k - 1) * pc.fact[k];
tmp %= MOD;
long tmp2 = (all - tmp + MOD) % MOD;
ans += tmp2 * i;
ans %= MOD;
// pr.printf("%d %d %d%n", i, tmp2, ans);
}
long tmp2 = (long)pc.P(n - 1, k);
ans += tmp2 * n;
ans %= MOD;
// pr.printf("%d %d %d%n", n, tmp2, ans);
pr.println(ans);
}
static class PC {
// MOD must be a prime number.
int MOD;
// fact[i] : i! % MOD
long[] fact;
// ifact[i] : 1/i! % MOD
long[] ifact;
PC(int size, int MOD) {
// O(size)
// n=sizeまでのnCrを求める。
// nHrはn+r-1Crになってしまうので注意
this.MOD = MOD;
fact = new long[size + 1];
fact[0] = 1;
for (int i = 1; i <= size; i++) {
fact[i] = fact[i - 1] * i % MOD;
}
ifact = new long[size + 1];
int loop = MOD - 2;
long x = fact[size];
ifact[size] = 1;
while (loop > 0) {
if (loop % 2 == 1) {
ifact[size] = ifact[size] * x % MOD;
}
x = x * x % MOD;
loop /= 2;
}
for (int i = size - 1; i >= 0; i--) {
ifact[i] = ifact[i + 1] * (i + 1) % MOD;
}
}
// 組合せの数
int C(int n, int r) {
if (r > n) {
return 0;
}
return (int)(((fact[n] * ifact[n - r]) % MOD) * ifact[r] % MOD);
}
// 順列
int P(int n, int r) {
if (r > n) {
return 0;
}
return (int)((fact[n] * ifact[n -r]) % MOD);
}
// 重複組み合わせ
// 異なるn種のものから重複を許してr個を選ぶ場合の数
// 0個の種類もあり得る
int H(int n, int r) {
if (n == 0 && r == 0) {
return 1;
}
return C(n + r - 1, r);
}
// 組合せの数(nが大きいとき)
// O(r)で求めることができる。rはsizeの大きさまで
int C2(long n, int r) {
long ret = ifact[r];
for (int i = 1; i <= r; i++) {
long tmp = (n - r + i) % MOD;
ret = (ret * tmp) % MOD;
}
return (int)ret;
}
// 第2種スターリング数
// n人をちょうどr個のグループに分ける(グループの区別はなし)
// グループの区別をする場合はr!S(n,r)。全射の場合の数と同義
// O(r log n)
int S(long n, int r) {
//全射の場合の数を包除原理を使って求めて、1/r!をかける。
long ret = 0;
for (int i = 1; i <= r; i++) {
long tmp = (r - i) % 2 == 0 ? 1 : -1;
tmp *= pow(i, n) * C(r, i) % MOD;
ret = (ret + tmp + MOD) % MOD;
}
ret = ret * ifact[r] % MOD;
return (int)ret;
}
long pow(int a, long n) {
long loop = n;
long ret = 1;
long x = a;
while (loop > 0) {
if (loop % 2 == 1) {
ret = ret * x % MOD;
}
x = x * x % MOD;
loop /= 2;
}
return ret;
}
// 組合せの数
// パスカルの三角形MODなし
// 限界：n=66 : 66C33=7219428434016265740
private final static int LIMIT = 66;
private static int to;
private static long[][] cache;
static long CLong(int n, int r) {
if (r > n) {
return 0;
}
if (n > LIMIT) {
throw new IllegalArgumentException(Integer.toString(n));
}
if (cache == null) {
cache = new long[LIMIT + 1][];
cache[0] = new long[1];
cache[0][0] = 1;
to = 0;
}
if (cache[n] == null) {
for (int i = to + 1; i <= n; i++) {
cache[i] = new long[i + 1];
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
cache[i][j] = 1;
} else {
if (Long.MAX_VALUE - cache[i - 1][j - 1] < cache[i - 1][j]) {
throw new IllegalArgumentException("Overflow");
} else {
cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j];
}
}
}
}
to = n;
}
return cache[n][r];
}
}
// ---------------------------------------------------
public static void main(String[] args) {
sc = new Scanner(System.in);
pr = new Printer(System.out);
solve();
pr.close();
sc.close();
}
static class Printer extends PrintWriter {
Printer(OutputStream out) {
super(out);
}
}
}