結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-07-01 10:01:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,955 bytes |
コンパイル時間 | 1,103 ms |
コンパイル使用メモリ | 105,200 KB |
実行使用メモリ | 15,380 KB |
最終ジャッジ日時 | 2024-09-13 20:53:27 |
合計ジャッジ時間 | 3,384 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 WA * 9 |
ソースコード
#include<algorithm>#include<algorithm> //sort,二分探索,など#include<bitset> //固定長bit集合#include<cmath> //pow,logなど#include<complex> //複素数#include<deque> //両端アクセスのキュー#include<functional> //sortのgreater#include<iomanip> //setprecision(浮動小数点の出力の誤差)#include<iostream> //入出力#include<iterator> //集合演算(積集合,和集合,差集合など)#include<map> //map(辞書)#include<numeric> //iota(整数列の生成),gcdとlcm(c++17)#include<queue> //キュー#include<set> //集合#include<stack> //スタック#include<string> //文字列#include<unordered_map> //イテレータあるけど順序保持しないmap#include<unordered_set> //イテレータあるけど順序保持しないset#include<utility> //pair#include<vector> //可変長配列using namespace std;typedef long long ll;typedef unsigned long long ull;typedef long double ld;typedef vector<int> vi;typedef vector<ll> vll;typedef vector<ld> vld;typedef vector<string> vs;typedef vector<bool> vb;typedef vector<vector<int>> vvi;typedef vector<vector<ll>> vvll;typedef vector<vector<ld>> vvld;typedef vector<vector<string>> vvs;typedef vector<vector<bool>> vvb;const ll MOD = 1000000007;const ll INF = 1000000000000000000;#define rep(i,n) for(int i=0;i<n;i++)#define repl(i,s,e) for(int i=s;i<e;i++)#define reple(i,s,e) for(int i=s;i<=e;i++)#define revrep(i,n) for(int i=n-1;i>=0;i--)#define all(x) (x).begin(),(x).end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }const int MAX = 510000;vector<ll> 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;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;}ll pmod(ll n, ll p) {ll m = n % MOD;if (p == 0) return 1;ll rtn = pmod((m * m) % MOD, p / 2) % MOD;if (p % 2 == 1) rtn = rtn * m % MOD;return rtn;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, M;cin >> N >> M;COMinit();ll ans = 0;reple(i, 0, M - 1){//包除原理の符号int s = i % 2 == 0 ? 1 : -1;ans += s * COM(M, M - i) * pmod(M - i, N);ans %= MOD;}cout << ans << endl;return 0;}