长春火车站停车场收费标准,企业网站建设代理,一个app下载网站,dede 网站名称不显示传送门 题意简述#xff1a;现在有一些号码由000~999中的某些数字组成#xff08;会给出#xff09;#xff0c;号码总长度为nnn#xff0c;问有多少个号码满足前n2\frac n22n个数码的和等于后n2\frac n22n个数码的和#xff08;保证nnn是偶数#xff09;#xff0… 传送门 题意简述现在有一些号码由000~999中的某些数字组成会给出号码总长度为nnn问有多少个号码满足前n2\frac n22n个数码的和等于后n2\frac n22n个数码的和保证nnn是偶数答案对998244353998244353998244353取模。 思路 一道挺显然的生成函数快速幂。 考虑到前n2\frac n22n个数码和的生成函数和后n2\frac n22n个数码和的生成函数是相同的因此直接求出前n2\frac n22n个数码和的生成函数然后对于每一项的系数平方加起来即可。 代码 #includebits/stdc.h
#define ri register int
using namespace std;
const int mod998244353,N2e55;
typedef long long ll;
int n,k,tim,lim;
vectorintA,B,pos;
inline void init(const intup){lim1,tim0;while(limup)lim1,tim;pos.resize(lim),A.resize(lim),B.resize(lim);for(ri i0;ilim;i)pos[i](pos[i1]1)|((i1)(tim-1));
}
inline int add(int a,int b){return abmod?ab-mod:ab;}
inline int dec(int a,int b){return ab?a-b:a-bmod;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret1;for(;p;p1,amul(a,a))if(p1)retmul(ret,a);return ret;}
inline void ntt(vectorinta,const inttype){for(ri i0;ilim;i)if(ipos[i])swap(a[i],a[pos[i]]);for(ri w,wn,typtype1?3:(mod1)/3,mult(mod-1)/2,mid1;midlim;mid1,mult1){wnksm(typ,mult);for(ri j0,lenmid1;jlim;jlen)for(ri w1,a0,a1,k0;kmid;k,wmul(w,wn)){a0a[jk],a1mul(w,a[jkmid]);a[jk]add(a0,a1),a[jkmid]dec(a0,a1);}}if(type-1)for(ri i0,invksm(lim,mod-2);ilim;i)a[i]mul(a[i],inv);
}
struct poly{vectorinta;poly(int k0,int x0){a.resize(k1),a[k]x;}inline intoperator[](const intk){return a[k];}inline const intoperator[](const intk)const{return a[k];}inline int deg()const{return a.size()-1;}inline poly extend(int k){poly ret*this;return ret.a.resize(k1),ret;}friend inline poly operator^(const polya,const intk){init(a.deg()*k);for(ri i0;ia.deg();i)A[i]B[i]a[i];for(ri ia.deg()1;ilim;i)A[i]B[i]0;int pk-1;ntt(A,1),ntt(B,1);while(p){if(p1)for(ri i0;ilim;i)B[i]mul(B[i],A[i]);for(ri i0;ilim;i)A[i]mul(A[i],A[i]);p1;}poly ret;return ntt(B,-1),ret.aB,ret.extend(a.deg()*k);}
};
int main(){poly a(9);int mx0;scanf(%d%d,n,k),n1;for(ri i1,v;ik;i)scanf(%d,v),a[v]1,mxmax(mx,v);aa.extend(mx);a(a^n);int ans0;for(ri i0;imx*n;i)ansadd(ans,mul(a[i],a[i]));coutans;return 0;
}转载于:https://www.cnblogs.com/ldxcaicai/p/10367716.html
