結果

問題 No.487 2017 Calculation(2017の計算)
ユーザー Goryudyuma
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 % mod
long 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 m
long 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0