結果

問題 No.1035 Color Box
ユーザー wk
提出日時 2020-04-24 23:11:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 4,001 bytes
コンパイル時間 1,546 ms
コンパイル使用メモリ 168,544 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 03:45:16
合計ジャッジ時間 2,765 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define INF 5000000000000000
using namespace std;
struct Edge{
int to;
long weight;
Edge(int t, long w) : to(t), weight(w) {}
};
long modpow(long a, long n, long mod) {
long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// a^{-1} mod
long modinv(long a, long mod) {
return modpow(a, mod - 2, mod);
}
struct compare1 {
bool operator()(const pair<long, long>& value,
const long& key)
{
return (value.first < key);
}
bool operator()(const long& key,
const pair<long, long>& value)
{
return (key < value.first);
}
};
struct UnionFind {
vector<int> par;
vector<int> rank;
UnionFind(int n = 1){
init(n);
}
void init(int n = 1){
par.resize(n);
rank.resize(n);
REP(i, n) par[i] = i, rank[i] = 0;
}
int root(int x){
if(par[x] == x) return x;
else return par[x] = root(par[x]);
}
bool issame(int x, int y){
return root(x) == root(y);
}
bool merge(int x, int y){
x = root(x); y = root(y);
if(x == y) return false;
if(rank[x] < rank[y]) swap(x, y);
if(rank[x] == rank[y]) rank[x]++;
par[y] = x;
return true;
}
};
template<class Abel> struct weightedUnionFind{
vector<int> par;
vector<int> rank;
vector<Abel> diff_weight;
weightedUnionFind(int n = 1, Abel SUM_UNITY = 0){
init(n, SUM_UNITY);
}
void init(int n = 1, Abel SUM_UNITY = 0){
par.resize(n); rank.resize(n); diff_weight.resize(n);
REP(i, n) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
}
int root(int x){
if(par[x] == x) return x;
else{
int r = root(par[x]);
diff_weight[x] += diff_weight[par[x]];
return par[x] = r;
}
}
Abel weight(int x){
root(x);
return diff_weight[x];
}
bool issame(int x, int y){
return root(x) == root(y);
}
bool merge(int x, int y, Abel w){
w += weight(x); w -= weight(y);
x = root(x); y = root(y);
if(x == y) return false;
if(rank[x] < rank[y]) swap(x, y), w = -w;
if(rank[x] == rank[y]) rank[x]++;
par[y] = x;
diff_weight[y] = w;
return true;
}
Abel diff(int x, int y){
return weight(y) - weight(x);
}
};
using Graph = vector<vector<int>>;
using P = pair<long, long>;
/*
void dijkstra(int s, int V, Graph &G, long* d){
priority_queue<P, vector<P>, greater<P>> pque;
fill(d, d + V, INF);
d[s] = 0;
pque.push(P(0, s));
while(!pque.empty()){
P p = pque.top(); pque.pop();
int now = p.second;
if(d[now] < p.first) continue;
REP(i, G[now].size()){
Edge e = G[now][i];
if(d[e.to] > d[now] + e.weight){
d[e.to] = d[now] + e.weight;
pque.push(P(d[e.to], e.to));
}
}
}
}
*/
long GCD(long a, long b){
if(b == 0l) return a;
if(a < b) return GCD(b, a);
else return GCD(b, a%b);
}
int main()
{
long N, M; cin >> N >> M;
long kai[100005], kai2[100005];
long mod = 1000000007;
kai[0] = 1l;
kai2[0] = 1l;
for(long i = 1l; i <= M; i++){
kai[i] = (i * kai[i-1l]) % mod;
kai2[i] = (modinv(i, mod) * kai2[i-1l]) % mod;
}
long ans = 0l;
for(long i = 0l; i <= M; i++){
long temp = kai[M] * kai2[i]; temp %= mod;
temp *= kai2[M-i]; temp %= mod;
temp *= modpow(M-i, N, mod); temp %= mod;
if(i%2==0){
ans += temp;
ans %= mod;
}else{
ans -= temp;
if(ans < 0l) ans += mod;
}
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0