結果
問題 | No.1100 Boxes |
ユーザー |
![]() |
提出日時 | 2020-09-23 17:02:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,903 bytes |
コンパイル時間 | 3,201 ms |
コンパイル使用メモリ | 236,168 KB |
最終ジャッジ日時 | 2025-01-14 19:49:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 RE * 8 TLE * 6 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/convolution>#include <atcoder/modint>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000000000struct FPS:vector<mint>{using vector<mint>::vector;FPS(const vector<mint> &x):vector<mint>(x){}FPS pow(long long n,int maxDegree = -1){if(maxDegree==-1)maxDegree = (*this).size() - 1;FPS now = (*this);FPS ret(1,1);while(n!=0){if(n&1){ret *= now;}n>>=1;if(n==0)break;now *= now;while(now.size()>maxDegree+1)now.pop_back();while(ret.size()>maxDegree+1)ret.pop_back();}while(ret.size()>maxDegree+1)ret.pop_back();return ret;}FPS inv(int maxDegree = -1){if(maxDegree==-1)maxDegree = (*this).size() - 1;FPS ret(1,(*this)[0].inv());int m = 1;while(m<maxDegree+1){ret = ret*2 - ret*ret*(*this);m *= 2;while(ret.size()>m)ret.pop_back();}while(ret.size()>maxDegree+1)ret.pop_back();return ret;}FPS &operator+=(mint another){*this += FPS(1,another);return (*this);}FPS operator+(mint another)const{return (FPS(*this)+=another);}FPS &operator+=(const FPS &another){if((*this).size()<another.size())(*this).resize(another.size(),0);rep(i,min((int)(*this).size(),(int)another.size())){(*this)[i] += another[i];}return (*this);}FPS operator+(const FPS &another)const{return (FPS(*this)+=another);}FPS operator-(){return (FPS(*this)*=-1);}FPS &operator-=(mint another){*this -= FPS(1,another);return (*this);}FPS operator-(mint another)const{return (FPS(*this)-=another);}FPS &operator-=(const FPS &another){if((*this).size()<another.size())(*this).resize(another.size(),0);rep(i,min((int)(*this).size(),(int)another.size())){(*this)[i] -= another[i];}return (*this);}FPS operator-(const FPS &another)const{return (FPS(*this)-=another);}FPS &operator*=(mint another){rep(i,(*this).size()){(*this)[i] *= another;}return (*this);}FPS operator*(mint another)const{return (FPS(*this)*=another);}FPS &operator*=(const FPS &another){FPS temp(convolution((*this),another));(*this) = temp;return (*this);}FPS operator*(const FPS &another)const{return (FPS(*this)*=another);}void show(){rep(i,(*this).size()){cout<<(*this)[i].val()<<',';}cout<<endl;}};int main(){int N,K;cin>>N>>K;FPS F(N+1,1);for(int i=1;i<=N;i++){F[i] = F[i-1] * i;}F.back() = F.back().inv();for(int i=N-1;i>=1;i--){F[i] = F[i+1] * (i+1);}FPS ans = F.pow(K,N);F -= 1;F = -F + 1;if(K&1){ans += F.pow(K,N);}else{ans -= F.pow(K,N);}mint Ans = ans[N];Ans /= 2;for(int i=1;i<=N;i++)Ans *= i;cout<<Ans.val()<<endl;return 0;}