結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
|
提出日時 | 2020-03-21 01:58:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 1,542 ms |
コンパイル使用メモリ | 167,108 KB |
実行使用メモリ | 15,452 KB |
最終ジャッジ日時 | 2024-07-17 11:56:13 |
合計ジャッジ時間 | 3,475 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = (n - 1); i >= 0; --i) #define ALL(obj) (obj).begin(), (obj).end() #define pb push_back #define to_s to_string #define len(v) (ll)v.size() #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) #define print(x) cout << (x) << '\n' #define debug(x) cout << #x << ": " << (x) << '\n' using namespace std; using ll = long long; typedef pair<ll, ll> P; ll MOD = 1e9 + 7; ll devc(ll x, ll y) { return 1 + (x - 1) / y; } const int MAX = 510000; long long fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int main() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); ll N, d, K; cin >> N >> d >> K; COMinit(); ll ans = 0; for(ll i = 0; i <= N; ++i){ ll tmp = 1; tmp *= COM(N + (K - N - d * i) - 1, (K - N - d * i)); tmp *= COM(N, i) % MOD; tmp *= i % 2 == 0 ? 1 : -1; ans += tmp + MOD; ans %= MOD; } print(ans); return 0; }