結果
問題 | No.1785 Inequality Signs |
ユーザー |
![]() |
提出日時 | 2021-12-23 16:21:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,856 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 44,032 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 14:59:03 |
合計ジャッジ時間 | 4,320 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 52 |
ソースコード
/* -*- coding: utf-8 -*-** 1785.cc: No.1785 Inequality Signs - yukicoder*/#include<cstdio>#include<algorithm>using namespace std;/* constant */const int MAX_N = 200000;const int MOD = 1000000007;/* typedef */template<const int MOD>struct MI {int v;MI(): v() {}MI(int _v): v(_v % MOD) {}MI(long long _v): v(_v % MOD) {}MI operator+(const MI m) const { return MI(v + m.v); }MI operator-(const MI m) const { return MI(v + MOD - m.v); }MI operator*(const MI m) const { return MI((long long)v * m.v); }MI &operator+=(const MI m) { return (*this = *this + m); }MI &operator-=(const MI m) { return (*this = *this - m); }MI &operator*=(const MI m) { return (*this = *this * m); }MI pow(int n) const { // a^n % MODMI pm = 1, a = *this;while (n > 0) {if (n & 1) pm *= a;a *= a;n >>= 1;}return pm;}MI inv() const { return pow(MOD - 2); }MI operator/(const MI m) const { return *this * m.inv(); }MI &operator/=(const MI m) { return (*this = *this / m); }};typedef MI<MOD> mi;/* global variables */mi fs[MAX_N + 1], invfs[MAX_N + 1];/* subroutines */inline mi nck(int n, int k) { // nCk % MODif (k < 0 || n < k) return 0;return fs[n] * invfs[n - k] * invfs[k];}void prepare_fracs(int n) {fs[0] = invfs[0] = 1;for (int i = 1; i <= n; i++) {fs[i] = fs[i - 1] * i;invfs[i] = fs[i].inv();}}/* subroutines *//* main */int main() {int n, k;scanf("%d%d", &n, &k);prepare_fracs(n);mi c = 0;if (k >= n) {c = invfs[n];for (int i = 0; i < n; i++) c *= k - i;}mi sum = 0;for (int i = 0; i < n; i++) {if (k + i < n) continue;if (k + i == n) c = 1;sum += c * nck(n - 1, i);c *= mi(k + i + 1) * mi(k + i + 1 - n).inv();}printf("%d\n", sum.v);return 0;}