結果
| 問題 |
No.1875 Flip Cards
|
| コンテスト | |
| ユーザー |
 ytqm3
|
| 提出日時 | 2021-12-22 21:09:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,755 bytes |
| コンパイル時間 | 3,372 ms |
| コンパイル使用メモリ | 222,916 KB |
| 最終ジャッジ日時 | 2025-01-27 05:36:26 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:427:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
427 | scanf("%d%d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:432:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
432 | scanf("%d%d%d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>
typedef uint64_t u64;
typedef int64_t i64;
using namespace std;
template<u64 mod> struct modint{
u64 val;
modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){}
modint operator-(){
return (val==0)?0:mod-val;
}
modint operator+(modint rhs){
return modint(*this)+=rhs;
}
modint operator-(modint rhs){
return modint(*this)-=rhs;
}
modint operator*(modint rhs){
return modint(*this)*=rhs;
}
modint operator/(modint rhs){
return modint(*this)/=rhs;
}
modint operator^(i64 rhs){
return modint(*this)^=rhs;
}
modint &operator+=(modint rhs){
val+=rhs.val,val-=((val>=mod)?mod:0);
return (*this);
}
modint &operator-=(modint rhs){
val+=((val<rhs.val)?mod:0),val-=rhs.val;
return (*this);
}
modint &operator*=(modint rhs){
val=val*rhs.val%mod;
return (*this);
}
modint &operator/=(modint rhs){
return (*this)*=rhs^(mod-2);
}
modint &operator^=(i64 rhs){
modint res=1,now=(*this);
while(rhs){
res*=((rhs&1)?now:1),now*=now,rhs>>=1;
}
return (*this)=res;
}
bool operator==(modint rhs){
return val==rhs.val;
}
bool operator!=(modint rhs){
return val!=rhs.val;
}
friend std::ostream &operator<<(std::ostream& os,modint x){
return os<<(x.val);
}
friend std::istream &operator>>(std::istream& is,modint& x){
u64 t;
is>>t,x=t;
return is;
}
};
template<u64 mod> struct NTT{
typedef modint<mod> mint;
mint g;
NTT(){
if(mod==998244353){
g=3;
return;
}
for(g=2;;g+=1){
if((g^((mod-1)>>1))!=1){
return;
}
}
}
void dft(vector<mint>& f){
int siz=f.size();
for(int i=1,j=0,t;i<siz;++i){
for(t=siz>>1;j&t;t>>=1){
j^=t;
}
if(i<(j^=t)){
swap(f[i],f[j]);
}
}
for(int b=1;b<siz;b<<=1){
mint zeta=g^((mod-1)/(2*b));
for(int i=0;i<siz;i+=2*b){
mint now=1;
for(int j=0;j<b;++j){
mint s=f[i+j],t=f[i+j+b]*now;
f[i+j]=s+t,f[i+j+b]=s-t;
now*=zeta;
}
}
}
}
vector<mint> operator()(vector<mint> a,vector<mint> b){
if(min(a.size(),b.size())<=100){
vector<mint> res(a.size()+b.size()-1,0);
for(size_t i=0;i<a.size();++i){
for(size_t j=0;j<b.size();++j){
res[i+j]+=a[i]*b[j];
}
}
return res;
}
int cnt=0,siz=1,mxsiz=a.size()+b.size()-1;
while(siz<mxsiz){
siz<<=1,++cnt;
}
a.resize(siz),b.resize(siz),dft(a),dft(b);
for(int i=0;i<siz;++i){
a[i]*=b[i];
}
dft(a),reverse(a.begin()+1,a.end()),a.resize(mxsiz);
mint isiz=mint(1)/siz;
for(int i=0;i<siz;++i){
a[i]*=isiz;
}
return a;
}
};
template<u64 mod> struct FPS{
typedef modint<mod> mint;
NTT<mod> ntt;
vector<mint> val;
FPS():val({0}){}
FPS(mint t):val({t}){}
FPS(int siz):val(max(1,siz)){}
FPS(initializer_list<modint<mod>> init):val(init){}
FPS(vector<mint> init):val(init){}
mint &operator[](int i){
return val[i];
}
int size(){
return val.size();
}
void resize(int siz){
val.resize(siz);
}
FPS& resize_(int siz){
auto tmp=val;
tmp.resize(siz);
return (*this)=tmp;
}
FPS operator-(){
for(mint& v:val){
v=mint(0)-v;
}
return (*this);
}
FPS& operator+=(mint rhs){
val[0]+=rhs;
return (*this);
}
FPS& operator-=(mint rhs){
val[0]-=rhs;
return (*this);
}
FPS& operator*=(mint rhs){
for(auto& v:val){
v*=rhs;
}
return (*this);
}
FPS& operator/=(mint rhs){
for(auto& v:val){
v/=rhs;
}
return (*this);
}
FPS operator+(mint rhs){
return FPS(*this)+=rhs;
}
FPS operator-(mint rhs){
return FPS(*this)-=rhs;
}
FPS operator*(mint rhs){
return FPS(*this)*=rhs;
}
FPS operator/(mint rhs){
return FPS(*this)/=rhs;
}
FPS& operator+=(FPS rhs){
resize(max(this->size(),rhs.size()));
for(int i=0;i<int(rhs.size());++i){
(*this)[i]+=rhs[i];
}
return (*this);
}
FPS& operator-=(FPS rhs){
resize(max(this->size(),rhs.size()));
for(int i=0;i<int(rhs.size());++i){
(*this)[i]-=rhs[i];
}
return (*this);
}
FPS& operator*=(FPS rhs){
val=ntt(val,rhs.val);
return (*this);
}
FPS& operator/=(FPS rhs){
val=ntt(val,rhs.inv().val);
return (*this);
}
FPS& operator>>=(int k){
if(int(val.size())<=k){
return (*this)={0};
}
FPS res=val;
res.val.erase(res.val.begin(),res.val.begin()+k);
return (*this)=res;
}
FPS& operator<<=(int k){
FPS res=val;
res.val.insert(res.val.begin(),k,mint(0));
return (*this)=res;
}
FPS operator+(FPS rhs){
return FPS(*this)+=rhs;
}
FPS operator-(FPS rhs){
return FPS(*this)-=rhs;
}
FPS operator*(FPS rhs){
return FPS(*this)*=rhs;
}
FPS operator/(FPS rhs){
return FPS(*this)/=rhs;
}
FPS operator<<(int k){
return FPS(*this)<<=k;
}
FPS operator>>(int k){
return FPS(*this)>>=k;
}
FPS shrink(){
for(int i=val.size()-1;i>0;--i){
if(val[i]==0){
val.pop_back();
}
else{
break;
}
}
return (*this);
}
FPS diff_(){
if(val.size()==1){
return (*this)={0};
}
FPS f(val.size()-1);
for(int i=1;i<val.size();++i){
f[i-1]=val[i]*i;
}
return f;
}
FPS integral_(){
FPS f(val.size()+1);
for(int i=0;i<val.size();++i){
f[i+1]=val[i]/(i+1);
}
return f;
}
FPS inv_(int mx=-1){
if(mx==-1){
mx=val.size();
}
if(val[0]==0){
assert(0);
}
FPS g({mint(1)/val[0]});
int now=1;
while(now<mx){
now<<=1;
FPS t=(*this);
t.resize(now);
t*=g;
t=-t+mint(2);
g*=t;
g.resize(now);
}
g.resize(mx);
return g;
}
FPS exp_(int mx=-1){
if(mx==-1){
mx=val.size();
}
if(val[0]!=0){
assert(0);
}
FPS g(mint(1));
int now=1;
while(now<mx){
now<<=1;
FPS t=(*this);
t.resize(now);
g*=t-g.log_(now)+mint(1);
g.resize(now);
}
g.resize(mx);
return g;
}
FPS log_(int mx=-1){
if(mx==-1){
mx=val.size();
}
if(val[0]!=1){
assert(0);
}
auto f=(*this);
f.resize(mx);
return (f.diff_()/f).integral_().resize_(mx);
}
FPS pow_(i64 k,int mx=-1){
if(mx==-1){
mx=val.size();
}
i64 t=0;
for(auto v:val){
if(v==0){
t++;
}
else{
break;
}
}
auto f=(*this)>>t;
if(f[0]==0){
f={0},f.resize(mx);
return f;
}
mint c=f[0];
f/=c;
(f.log(mx)*=mint(k)).exp(mx)*=(c^k);
if(t*k<=mx){
f<<=t*k;
f.resize(mx);
return f;
}
else{
f={0},f.resize(mx);
return f;
}
}
FPS& diff(){
return (*this)=diff_();
}
FPS& integral(){
return (*this)=integral_();
}
FPS& inv(int mx=-1){
return (*this)=inv_(mx);
}
FPS& exp(int mx=-1){
return (*this)=exp_(mx);
}
FPS& log(int mx=-1){
return (*this)=log_(mx);
}
FPS& pow(i64 k,int mx=-1){
return (*this)=pow_(k,mx);
}
};
template<u64 mod> FPS<mod> product(vector<FPS<mod>> a){
int siz=1;
while(siz<int(a.size())){
siz<<=1;
}
vector<FPS<mod>> res(siz*2-1,{1});
for(int i=0;i<int(a.size());++i){
res[i+siz-1]=a[i];
}
for(int i=siz-2;i>=0;--i){
res[i]=res[2*i+1]*res[2*i+2];
}
return res[0];
}
template<u64 mod> FPS<mod> inv_sum(int M,vector<FPS<mod>> f){
int siz=1;
while(siz<int(f.size())){
siz<<=1;
}
vector<FPS<mod>> mol(siz*2-1),den(siz*2-1,{1});
for(size_t i=0;i<f.size();++i){
mol[i+siz-1]={1};
den[i+siz-1]=f[i];
}
for(int i=siz-2;i>=0;--i){
den[i]=den[2*i+1]*den[2*i+2];
mol[i]=mol[2*i+1]*den[2*i+2]+mol[2*i+2]*den[2*i+1];
}
mol[0]*=den[0].inv(M+1);
return mol[0].resize_(M+1);
}
template<u64 mod> vector<modint<mod>> stirling_number2(int N){
typedef modint<mod> mint;
FPS<mod> f(N+1),g(N+1);
mint fact=1;
for(int i=0;i<=N;++i){
f[i]=(mint(i)^N)/fact;
g[i]=(mint(-1)^i)/fact;
fact*=i+1;
}
f*=g;
vector<mint> res(N+1);
for(int i=0;i<=N;++i){
res[i]=f[i];
}
return res;
}
int main(){
constexpr u64 mod=998244353;
typedef modint<mod> mint;
int N,M;
scanf("%d%d",&N,&M);
mint prod=1;
vector<FPS<mod>> f(N);
for(int i=0;i<N;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
prod*=mint(a)^c;
mint u=mint(a)/b,v=mint(1)/c;
f[i]={u*v,v};
}
auto g=inv_sum(M,f);
g.integral();
g.exp();
auto Sm=stirling_number2<mod>(M);
mint ans=0,fact=1;
for(int i=0;i<=M;++i){
ans+=Sm[i]*fact*prod*g[i];
fact*=i+1;
}
printf("%d\n",int(ans.val));
}