Solution CF438E The Child and Binary Tree
题目大意：给定正整数集合 (c)。(forall s in[1,m])，求出有多少个有根二叉树，满足每个点的点权都在集合 (c) 中，且所有点的点权之和为 (s)。答案对 (998244353) 取模。
NTT，多项式开根
分析：
我们尝试着搞一个生成函数出来，令 ([x^s]F(x)) 表示得到点权之和为 (s) 的方案数
转移就是一个树形背包，也就是卷积的形式
([x^s]F(x)=sum_{i=1}^{n}[x^{s-c_i}]F^2(x))
然后这个东西还是一个卷积
我们设一个 (G)，(forall c_i in cquad[x^{c_i}]G(x)=1)
也就是说 (F-1 equiv F^2G quad (mod;x^m))（因为可能子树为空，所以我们要求 ([x^0]F(x)=1)）
代入求根公式，我们要求的就是这个 (F equiv frac{1 pm sqrt{1-4G}}{2G} quad (mod;x^m))
但是 (G) 的常数项为 (0)，在模 (x^m) 意义下没有乘法逆
做一点变形
(Fequivfrac{(1-sqrt{1-4G})(1+sqrt{1-4G})}{2G(1+sqrt{1-4G})}equivfrac{2}{1+sqrt{1-4G}}quad(mod;x^m))
直接多项式开根，多项式求逆就可以了
萌新刚学多项式，有问题请多指教 /kel
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#pragma GCC optmize(2)
using namespace std;
typedef long long ll;
constexpr int maxn = 4e5 + 100,mod = 998244353,G = 3,invG = 332748118,inf = 0x7fffffff;
constexpr inline int add(const int a,const int b){return (a + b) % mod;}
constexpr inline int sub(const int a,const int b){return (a - b + mod) % mod;}
constexpr inline int mul(const int a,const int b){return (1ll * a * b) % mod;}
inline int qpow(int base,int b){
int res = 1;
while(b){
if(b & 1)res = mul(res,base);
base = mul(base,base);
b >>= 1;
}
return res;
}
inline int inv(const int x){return qpow(x,mod - 2);}
struct IO{//-std=c++11,with cstdio and cctype
private:
static constexpr int ibufsiz = 1 << 20;
char ibuf[ibufsiz + 1],*inow = ibuf,*ied = ibuf;
static constexpr int obufsiz = 1 << 20;
char obuf[obufsiz + 1],*onow = obuf;
const char *oed = obuf + obufsiz;
public:
inline char getchar(){
#ifndef ONLINE_JUDGE
return ::getchar();
#else
if(inow == ied){
ied = ibuf + sizeof(char) * fread(ibuf,sizeof(char),ibufsiz,stdin);
*ied = ' ';
inow = ibuf;
}
return *inow++;
#endif
}
template<typename T>
inline void read(T &x){
static bool flg;flg = 0;
x = 0;char c = getchar();
while(!isdigit(c))flg = c == '-' ? 1 : flg,c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
if(flg)x = -x;
}
template <typename T,typename ...Y>
inline void read(T &x,Y&... X){read(x);read(X...);}
inline int readi(){static int res;read(res);return res;}
inline long long readll(){static long long res;read(res);return res;}
inline void flush(){
fwrite(obuf,sizeof(char),onow - obuf,stdout);
fflush(stdout);
onow = obuf;
}
inline void putchar(char c){
#ifndef ONLINE_JUDGE
::putchar(c);
#else
*onow++ = c;
if(onow == oed){
fwrite(obuf,sizeof(char),obufsiz,stdout);
onow = obuf;
}
#endif
}
template <typename T>
inline void write(T x,char split = ' '){
static unsigned char buf[64];
if(x < 0)putchar('-'),x = -x;
int p = 0;
do{
buf[++p] = x % 10;
x /= 10;
}while(x);
for(int i = p;i >= 1;i--)putchar(buf[i] + '0');
if(split != ' ')putchar(split);
}
inline void lf(){putchar('
');}
~IO(){
fwrite(obuf,sizeof(char),onow - obuf,stdout);
}
}io;
template <typename A,typename B>
inline void chkmin(A &x,const B &y){if(y < x)x = y;}
template <typename A,typename B>
inline void chkmax(A &x,const B &y){if(y > x)x = y;}
int tr[maxn << 1],len = 1;
struct poly : std::vector<int>{
using std::vector<int>::vector;
#define f (*this)
inline void ntt(const int flg = 1){
const int n = size();
for(int i = 0;i < n;i++)
if(i < tr[i])std::swap(f[i],f[tr[i]]);
for(int p = 2;p <= n;p <<= 1){
const int unit = qpow(flg == 1 ? G : invG,(mod - 1) / p);
const int len = p >> 1;
for(int k = 0;k < n;k += p){
int now = 1;
for(int l = k;l < k + len;l++){
const int tt = mul(f[l + len],now);
f[l + len] = sub(f[l],tt);
f[l] = add(f[l],tt);
now = mul(now,unit);
}
}
}
if(flg == -1){
const int inv = ::inv(n);
for(int i = 0;i < n;i++)f[i] = mul(f[i],inv);
}
}
poly operator + (const poly &g)const{
poly res;res.resize(size());
for(unsigned int i = 0;i < size();i++)res[i] = add(f[i],g[i]);
return res;
}
poly operator * (const poly &g)const{
poly res;res.resize(size());
for(unsigned int i = 0;i < size();i++)res[i] = mul(f[i],g[i]);
return res;
}
poly operator * (const int g)const{
poly res;res.resize(size());
for(unsigned int i = 0;i < size();i++)res[i] = mul(f[i],g);
return res;
}
poly operator - (const poly &g)const{
poly res;res.resize(size());
for(unsigned int i = 0;i < size();i++)res[i] = sub(f[i],g[i]);
return res;
}
inline void print()const{
fprintf(stderr,"siz=%d :",(int)size());
for(int x : (*this))fprintf(stderr,"%d ",x);
fprintf(stderr,"
");
}
#undef f
};
inline poly calc(poly a,poly &&b){//2 * b - a * b ^ 2
for(len = 1;len < a.size() + b.size() + b.size() - 2;len <<= 1);
for(int i = 0;i < len;i++)
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
a.resize(len);
b.resize(len);
a.ntt();
b.ntt();
poly &&res = b * 2 - a * b * b;
res.ntt(-1);
return res;
}
inline poly inv(const poly &x){
if(x.size() == 1)return poly{inv(x[0])};
poly tmp(x);
tmp.resize((x.size() + 1) >> 1);
tmp = calc(x,inv(tmp));
tmp.resize(x.size());
return tmp;
}
inline poly sqrt(const poly &x){
if(x.size() == 1)return poly{1};
poly t(x);t.resize((x.size() + 1) >> 1);t = sqrt(t);
poly g(x);
poly inv = t * 2;
inv.resize(x.size());
inv = ::inv(inv);
for(len = 1;len < t.size() + t.size() + inv.size() - 2;len <<= 1);
for(int i = 0;i < len;i++)
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
t.resize(len);g.resize(len);inv.resize(len);
t.ntt();g.ntt();inv.ntt();
poly res = (t * t + g) * inv;
res.ntt(-1);
res.resize(x.size());
return res;
}
int main(){
const int n = io.readi(),m = io.readi();
poly g;
g.resize(1e5 + 1);
for(int i = 1;i <= n;i++)g[io.readi()] = 1;
g.resize(m + 1);
for(unsigned int i = 0;i < g.size();i++)g[i] = sub(0,4 * g[i]);
g[0] = add(g[0],1);
g = sqrt(g);
g[0] = add(g[0],1);
g.resize(m + 1);
g = inv(g);
poly f;
f.resize(m + 1);
f[0] = 2;
for(int len = 1;len < g.size() + f.size() - 1;len <<= 1);
for(int i = 0;i < len;i++)tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
f.resize(len);g.resize(len);
f.ntt();g.ntt();
poly ans = f * g;
ans.ntt(-1);
for(int i = 1;i <= m;i++)io.write(ans[i],'
');
return 0;
}