Submission #71701105

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;bool Mbe;
namespace MAOJUN{

typedef long long ll;
const int N=105,S=1e4+5,P=998244353;
int n,a[N];ll m;

inline ll ksm(ll x,int y=P-2){ll r=1;for(;y;y>>=1,x=x*x%P)if(y&1)r=r*x%P;return r;}
const int K=17,Z=1<<K,G=3,iG=(P+1)/3;
struct MG{int*mG[2][K];MG(){
    for(int o=0;o<2;o++)for(int k=0;k<K;k++){
        const ll w=ksm(o?G:iG,P>>k+1);
        mG[o][k]=new int[1<<k];mG[o][k][0]=1;
        for(int j=1;j<1<<k;j++)mG[o][k][j]=mG[o][k][j-1]*w%P;
    }
}}Mg;int*(&mG)[2][K]=Mg.mG,Ln,Iv,Rv[Z];
inline void IIT(int n){
	int l=__lg(n*2-1);Ln=1<<l;Iv=P-(P>>l--);
	for(int i=0;i<Ln;i++)Rv[i]=Rv[i>>1]>>1|(i&1)<<l;
}
inline int ad(int x,int y){x+=y;return x>=P?x-P:x;}
inline void NTT(int*A,int o){
	for(int i=0;i<Ln;i++)if(i<Rv[i])swap(A[i],A[Rv[i]]);
	for(int k=0;1<<k<Ln;k++)for(int i=0;i<Ln;i+=1<<k+1)for(int j=0;j<1<<k;j++){
		int x=A[i|j],y=(ll)A[i|1<<k|j]*mG[o][k][j]%P;
		A[i|j]=ad(x,y);A[i|1<<k|j]=ad(x,P-y);
	}
	if(!o)for(int i=0;i<Ln;i++)A[i]=(ll)A[i]*Iv%P;
}

int f[Z],A[Z],B[Z],C[Z],D[Z],E[Z];
inline void main(){
	scanf("%d%lld",&n,&m);a[0]=1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int z=0;f[0]=1;
	for(int i=0;i<=n;i++){
		z+=a[i];
		for(int j=z;j>=a[i];j--)f[j]=ad(f[j],P-f[j-a[i]]);
	}
	z=5e4;
	A[0]=1;
	for(int i=0;i<=z;i++)B[i]=f[i];
	IIT(z+z+1);
	for(;m;m>>=1){
		memcpy(C,B,sizeof C);
		for(int i=1;i<=z;i+=2)C[i]=(P-C[i])%P;
		NTT(A,1);NTT(B,1),NTT(C,1);
		for(int i=0;i<Ln;i++){D[i]=(ll)A[i]*C[i]%P;E[i]=(ll)B[i]*C[i]%P;}
		NTT(D,0);NTT(E,0);
		memset(A,0,sizeof A);
		memset(B,0,sizeof B);
		for(int i=m&1;i<=z;i+=2)A[i>>1]=D[i];
		for(int i=0;i<=z;i+=2)B[i>>1]=E[i];
	}
	printf("%lld\n",A[0]*ksm(B[0])%P);
}

}bool Med;int main(){
#ifdef IO
	freopen("2.in","r",stdin);
	freopen("data.out","w",stdout);
#endif
#ifdef TM
	atexit([](){fprintf(stderr,"%.0lfms\n%lfMB\n",clock()*1000./CLOCKS_PER_SEC,(&Mbe-&Med)/1024./1024);});
#endif
	MAOJUN::main();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In constructor 'MAOJUN::MG::MG()':
./Main.cpp:13:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         const ll w=ksm(o?G:iG,P>>k+1);
      |                                  ~^~
./Main.cpp: In function 'void MAOJUN::NTT(int*, int)':
./Main.cpp:25:57: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   25 |         for(int k=0;1<<k<Ln;k++)for(int i=0;i<Ln;i+=1<<k+1)for(int j=0;j<1<<k;j++){
      |                                                        ~^~

Judge Result