結果
問題 | No.1035 Color Box |
ユーザー |
|
提出日時 | 2020-04-24 23:17:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,980 bytes |
コンパイル時間 | 763 ms |
コンパイル使用メモリ | 83,828 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 03:49:09 |
合計ジャッジ時間 | 1,977 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;class binomial_coefficients {long long MAX_VAL;public:vector<long long> fac, mmi;binomial_coefficients(){}binomial_coefficients(long long num){init(num);}~binomial_coefficients(){}void init(long long num){MAX_VAL = num+1;fac.resize(MAX_VAL);mmi.resize(MAX_VAL);factorial_mod();modular_multiplicatibe_inverse();}void factorial_mod(){fac[0] = 1;for(long long i = 1; i < MAX_VAL; fac[i] %= MOD, i++)fac[i] = fac[i - 1] * (i % MOD);}long long power(long long x, long long n){long long ans = 1;for(;n;n >>= 1, x *= x, ans %= MOD, x %= MOD)if(n&1)ans*=x;return ans % MOD;}void exgcd(long long a, long long b, long long &x, long long &y){if(b == 0){x = 1;y = 0;return ;}exgcd(b, a % b, y, x);y -= a / b * x;}void modular_multiplicatibe_inverse(){long long x, y;exgcd(fac[MAX_VAL - 1], MOD, x, y);mmi[MAX_VAL-1] = x;// mmi[MAX_VAL-1] = power(fac[MAX_VAL-1], MOD-2);for(long long i = MAX_VAL - 2; i >= 0; mmi[i]%=MOD, i--)mmi[i] = mmi[i + 1] * ((i + 1) % MOD);}long long combination(long long n, long long r){return n < r ? 0 :fac[n] * (mmi[r] * mmi[n-r] % MOD) % MOD;}};signed main(){cout<<fixed<<setprecision(10);int N, M;int ans = 0;binomial_coefficients BC;cin>>N>>M;BC.init(N+2);for(int i = 1; i <= M; i++){if((M - i)%2) {ans += MOD - (BC.combination(M, i) * BC.power(i, N))%MOD;} else {ans += (BC.combination(M, i) * BC.power(i, N))%MOD;}ans %= MOD;}cout<<ans<<endl;return 0;}