結果
問題 | No.487 2017 Calculation(2017の計算) |
ユーザー |
|
提出日時 | 2017-04-07 20:20:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,188 bytes |
コンパイル時間 | 1,657 ms |
コンパイル使用メモリ | 169,808 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-16 00:36:32 |
合計ジャッジ時間 | 2,374 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>#define DEBUG 0/**/using namespace std;class combination{public://Nの最大値がわかれば代入するcombination(long long int combinationThreshold = 1e7) {(*this).combinationThreshold = combinationThreshold + 2;}//a^p % modlong long int powmod(long long int A, long long int P, long long int M = LLONG_MAX) {long long int ans = 1;long long int mul = A;for (; P > 0; P >>= 1, mul = (mul*mul) % M) {if ((P & 1) == 1) ans = (ans*mul) % M;}return ans;}//nCk mod mlong long int cb(long long int N, long long int K, long long int M = LLONG_MAX) {if (N < combinationThreshold) {// 事前計算O(N)、答えるのはO(1)if (inv.size() == 0) {inv = vector<long long int>(combinationThreshold);inv[1] = 1;for (long long int i = 2; i < combinationThreshold; i++) {inv[i] = M - (M / i)*inv[M%i] % M;}fact = vector<long long int>(combinationThreshold);fact[0] = 1;revFact = vector<long long int>(combinationThreshold);revFact[0] = 1;for (long long int i = 1; i < combinationThreshold; i++) {fact[i] = (fact[i - 1] * i) % M;revFact[i] = (revFact[i - 1] * inv[i]) % M;}}return (((fact[N] * revFact[K]) % M)*revFact[N - K]) % M;}else {return cbOnce(N, K, M);}}//一回だけなら最速 O(K + log(M))long long int cbOnce(long long int N, long long int K, long long int M = LLONG_MAX) {if (K > N / 2) return cb(N, N - K, M);long long int ans = 1;long long int div = 1;for (long long int i = 0; i < K; i++) {ans *= N - i;ans %= M;div *= i + 1;div %= M;}ans *= powmod(div, M - 2, M);return ans%M;}private:vector<vector<long long int>>C;//3000以下の答えvector<long long int>fact;//階乗vector<long long int>revFact;//階乗の逆元vector<long long int>inv;//mod pでの逆元long long int combinationThreshold;//Nの最大値がわかれば入れる。};int main() {combination cb;long long int M;cin >> M;cout << (2017 + cb.powmod(2017 * 2017, 2017, M)) % M << endl;if (DEBUG){int ewataeoprgjpsrteog;cin >> ewataeoprgjpsrteog;}}