結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2019-02-27 05:47:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,737 bytes |
コンパイル時間 | 1,070 ms |
コンパイル使用メモリ | 97,528 KB |
実行使用メモリ | 19,132 KB |
最終ジャッジ日時 | 2024-06-23 05:01:43 |
合計ジャッジ時間 | 2,731 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream> #include <bitset> #include <fstream> #include <string> #include <cstring> #include <cmath> #include <cstdlib> #include <ctime> #include <vector> #include <algorithm> #include <numeric> #include <map> #include <set> #include <stack> #include <queue> #include <deque> #include <functional> #include <cctype> #include <list> #include <limits> //#include <boost/multiprecision/cpp_int.hpp> const double EPS = (1e-10); using namespace std; using Int = long long; //using namespace boost::multiprecision; const Int MOD = 1000000007; const int MAXN = 1000000; Int fact[MAXN], inv[MAXN]; Int mod_pow(Int x, Int n) { Int res = 1; while(n > 0) { if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき) x = (x * x) % MOD; n >>= 1; //右シフト(n = n >> 1) } return res; } void init_fact() { fact[0] = 1; for(int i=1; i<MAXN; i++) { fact[i] = (fact[i-1] * i) % MOD; } inv[MAXN - 1] = mod_pow(fact[MAXN - 1], MOD-2); for(int i=MAXN - 2; i>=0; i--) { inv[i] = (inv[i+1] * (i+1)) % MOD; } } Int comb(int n, int r) { if(r < 0 || n < r) return 0; return fact[n] * inv[n-r] % MOD * inv[r] % MOD; } template<typename T> T gcd(T a, T b) { return b != 0 ? gcd(b, a % b) : a; } template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); } int main(){ cin.tie(0); int N, M; cin >> N >> M; Int ans = 0; init_fact(); for (int i = 1; i <= M; i++){ if ((M-i)%2){ ans += -1LL*(comb(M, i)*mod_pow(i, N))%MOD; }else{ ans += (comb(M, i)*mod_pow(i, N))%MOD; } ans += MOD; ans %= MOD; } cout << ans << endl; }