結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:35:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,272 bytes |
コンパイル時間 | 2,226 ms |
コンパイル使用メモリ | 198,268 KB |
最終ジャッジ日時 | 2025-01-09 23:18:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 1000000000000000001//aのb乗int beki(int a,int b,int M = modulo){int x = 1;while(b!=0){if(b&1){x=((long long)x*a)%M;}a=((long long)a*a)%M;b>>=1;}return x;}//aの逆元int gyakugen(int a){return beki(a,modulo-2);}struct combi{deque<int> kaijou;deque<int> kaijou_;combi(int n){kaijou.push_back(1);for(int i=1;i<=n;i++){kaijou.push_back(mod(kaijou[i-1]*i));}int b=gyakugen(kaijou[n]);kaijou_.push_front(b);for(int i=1;i<=n;i++){int k=n+1-i;kaijou_.push_front(mod(kaijou_[0]*k));}}int combination(int n,int r){if(r>n)return 0;int a = mod(kaijou[n]*kaijou_[r]);a=mod(a*kaijou_[n-r]);return a;}int junretsu(int a,int b){int x = mod(kaijou_[a]*kaijou_[b]);x=mod(x*kaijou[a+b]);return x;}int catalan(int n){return mod(combination(2*n,n)*gyakugen(n+1));}};int main(){int N,M;cin>>N>>M;int ans = 0;combi C(400000);for(int i=M;i>=1;i--){int c = C.combination(M,i);c = mod(c * beki(i,N));if((M-i)%2==0)ans = mod(ans + c);else ans = mod(ans - c);}cout<<ans<<endl;return 0;}