結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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

#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 1000000000000000
struct 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0