深圳网站建设推广优化seo,做公司官网多少钱,手机免费做网页的软件,泉州网页搜索排名提升传送门codeforces传送门codeforces传送门codeforces传送门 生成函数好题。 卡场差评至今未过 题意简述#xff1a;nnn个点的二叉树#xff0c;每个点的权值KaTeX parse error: Expected EOF, got \inC at position 4: v_i\̲i̲n̲C̲\{a_1,a_2,...a…#xff0c;定义一棵树… 传送门codeforces传送门codeforces传送门codeforces传送门 生成函数好题。 卡场差评至今未过 题意简述nnn个点的二叉树每个点的权值KaTeX parse error: Expected EOF, got \inC at position 4: v_i\̲i̲n̲C̲\{a_1,a_2,...a…定义一棵树的权值为所有点的权值之和问有多少棵树满足其权值等于i(i1,2,...,m)i(i1,2,...,m)i(i1,2,...,m) 对每个点的值构造生成函数g(x)∑nanxn(an[n∈C])g(x)\sum_na_nx^n(a_n[n\in C])g(x)∑nanxn(an[n∈C])令f(x)f(x)f(x)表示答案的生成函数。 那么f(x)g(x)f2(x)1f(x)g(x)f^2(x)1f(x)g(x)f2(x)1 注意空树的情况这个递推式相当于考虑自己的权值以及左右子树的权值 然后解方程f(x)21−1−4g(x)f(x)\frac 2{1-\sqrt{1-4g(x)}}f(x)1−1−4g(x)2 然后上多项式开方和多项式求逆即可。 悲伤的故事封装了一波多项式运算导致常数太大于是只能在codeforcescodeforcescodeforces上水过bzojbzojbzoj至今未过 代码 #includebits/stdc.h
#define ri register int
using namespace std;
inline int read(){int ans0;char chgetchar();while(!isdigit(ch))chgetchar();while(isdigit(ch))ans(ans3)(ans1)(ch^48),chgetchar();return ans;
}
typedef long long ll;
const int mod998244353;
int n,lim,tim,m;
vectorintA,B,pos,Inv;
#define add(a,b) ((a)(b)mod?(a)(b)-mod:(a)(b))
#define dec(a,b) ((a)(b)?(a)-(b):(a)-(b)mod)
#define mul(a,b) ((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 mid1,wn,mult(mod-1)/2,typtype1?3:(mod1)/3;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);
}
inline void init(const intup){lim1,tim0;while(limup)lim1,tim;pos.resize(lim),pos[0]0;for(ri i0;ilim;i)pos[i](pos[i1]1)|((i1)(tim-1));
}
struct poly{vectorinta;inline int deg()const{return a.size()-1;}poly(int k,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 poly extend(const intk){poly ret*this;return ret.a.resize(k),ret;}friend inline poly operator(const polya,const polyb){poly ret(max(a.deg(),b.deg()));for(ri i0;ia.deg();i)ret[i]add(ret[i],a[i]);for(ri i0;ib.deg();i)ret[i]add(ret[i],b[i]);return ret;}friend inline poly operator-(const polya,const polyb){poly ret(max(a.deg(),b.deg()));for(ri i0;ia.deg();i)ret[i]add(ret[i],a[i]);for(ri i0;ib.deg();i)ret[i]dec(ret[i],b[i]);return ret;}friend inline poly operator*(const inta,const polyb){poly ret(b.deg());for(ri i0;ib.deg();i)ret[i]mul(a,b[i]);return ret;}friend inline poly operator*(const polya,const polyb){int na.deg(),mb.deg();init(nm),A.resize(lim),B.resize(lim);poly ret(lim-1);for(ri i0;in;i)A[i]a[i];for(ri i0;im;i)B[i]b[i];for(ri in1;ilim;i)A[i]0;for(ri im1;ilim;i)B[i]0;ntt(A,1),ntt(B,1);for(ri i0;ilim;i)A[i]mul(A[i],B[i]);return ntt(A,-1),ret.aA,ret;}inline poly poly_inv(poly a,const intk){aa.extend(k);if(k1)return poly(0,ksm(a[0],mod-2));poly f0poly_inv(a,(k1)1);return (2*f0-((f0*f0.extend(k))*a).extend(k)).extend(k);}inline poly poly_sqrt(poly a,const intk){aa.extend(k);if(k1)return poly(0,1);poly f0poly_sqrt(a,(k1)1).extend(k);return (((f0*f0).extend(k)a)*poly_inv((2*f0),k)).extend(k);}
};
int main(){nread(),mread();int len;for(len1;lenm;len1);poly sqr(len);for(ri i1,v;in;i){vread();if(vm)sqr[v]mod-4;}sqr[0],sqrsqr.poly_sqrt(sqr,len),sqr[0],sqrsqr.poly_inv(sqr,len);for(ri i1;im;i)coutmul(sqr[i],2)\n;return 0;
}转载于:https://www.cnblogs.com/ldxcaicai/p/10367793.html
