微网站是用什么开发的,昆明网页制作,做零食网站怎么样,商标注册网上申请平台提供一个多项式做法。
分别设 f u , i , g u , i f_{u,i},g_{u,i} fu,i,gu,i表示以 u u u为根时#xff0c; a u i a_ui aui和 a u ≥ i a_u\ge i au≥i的方案数#xff0c;合并子树 v v v时#xff0c;转移如下#xff1a; f u , i ∑ f u , i − k r g v . k…提供一个多项式做法。
分别设 f u , i , g u , i f_{u,i},g_{u,i} fu,i,gu,i表示以 u u u为根时 a u i a_ui aui和 a u ≥ i a_u\ge i au≥i的方案数合并子树 v v v时转移如下 f u , i ∑ f u , i − k r × g v . k f_{u,i}\sum f_{u,i-kr}\times g_{v.k} fu,i∑fu,i−kr×gv.k
初值为 f u , a u 1 f_{u,a_u}1 fu,au1。
注意到 DP 的值域很大通常情况下我们可以考虑用拉格朗日插值法来处理但是实际上只要满足信息封闭也是可以转移的。我们不妨将其转化成多项式的形式从而来观察需要记录哪些信息。
设 F u ( x ) ∑ f u , i x i G u ( x ) ∑ g u , i x i F_u(x)\sum f_{u,i}x^i\\G_u(x)\sum g_{u,i}x^i Fu(x)∑fu,ixiGu(x)∑gu,ixi
转移大致分为以下几步 F u ( x ) ← ∏ G v ( x ) F u ( x ) ← x a i F u ( x r ) G u ( x ) ← F u ( x ) F u ( 1 ) − F u ( x ) 1 − x F_u(x)\gets \prod G_v(x)\\F_u(x)\gets x^{a_i}F_u(x^r)\\ G_u(x)\gets F_u(x)\frac{F_u(1)-F_u(x)}{1-x} Fu(x)←∏Gv(x)Fu(x)←xaiFu(xr)Gu(x)←Fu(x)1−xFu(1)−Fu(x)
其中最后一个式子是在求后缀和之所以不能写成 1 1 − x − 1 \frac{1}{1-x^{-1}} 1−x−11的原因是生成函数不能有次数 0 0 0的项。
现在问题在于要求出 F u ( 1 ) F_u(1) Fu(1)就必须维护各项系数显然次数太高就寄了。考虑一步非常巧妙的转化我们设 G u ′ ( x ) G u ( x 1 ) , F u ′ ( x ) F u ( x 1 ) G_u(x)G_u(x1),F_u(x)F_u(x1) Gu′(x)Gu(x1),Fu′(x)Fu(x1)则 F u ′ ( 0 ) F u ( 1 ) F_u(0)F_u(1) Fu′(0)Fu(1)而 F u ′ ( 0 ) F_u(0) Fu′(0)其实就是常数项又因为要求的答案也是常数项这样我们只用算次数较低的项信息就封闭了。
新的转移大致为 F u ′ ( x ) ← ∏ G v ′ ( x ) F_u(x)\gets \prod G_v(x)\\ Fu′(x)←∏Gv′(x)
这是因为 F u ′ ( x ) F u ( x 1 ) ∏ G v ( x 1 ) ∏ G v ′ ( x ) F_u(x)F_u(x1)\prod G_v(x1)\prod G_v(x) Fu′(x)Fu(x1)∏Gv(x1)∏Gv′(x) F u ′ ( x ) ← ( x 1 ) a i F u ′ ( ( x 1 ) r − 1 ) F_u(x)\gets (x1)^{a_i}F_u((x1)^r-1) Fu′(x)←(x1)aiFu′((x1)r−1)
这是因为 F u ′ ( x ) F u ( x 1 ) ( x 1 ) a i F u ( ( x 1 ) r ) ( x 1 ) a i F u ′ ( ( x 1 ) r − 1 ) F_u(x)F_u(x1)(x1)^{a_i}F_u((x1)^r)(x1)^{a_i}F_u((x1)^r-1) Fu′(x)Fu(x1)(x1)aiFu((x1)r)(x1)aiFu′((x1)r−1) G u ′ ( x ) F u ′ ( x ) F u ′ ( 0 ) − F u ′ ( x ) − x G_u(x)F_u(x)\frac{F_u(0)-F_u(x)}{-x} Gu′(x)Fu′(x)−xFu′(0)−Fu′(x)
如果我们只保留前 k k k项那么因为要除以 x x x所以每次转移完后最后一项都会损失掉。但是因为答案是第一项的值所以我们对于每个节点保留 d e p u dep_u depu项即可。
复杂度 O ( n 3 ) O(n^3) O(n3)。
麻了好像和官方题解长得一样。
#includebits/stdc.h
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int mod998244353;
int n,fa[305],dep[305];
ll r,fac[305],inv[305],ifac[305],to[305][305],f[305][305],g[305][305],a[305],res;
vectorintG[305];
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
ll binom(int x,int y){if(x0||y0||xy)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(int n){fac[0]1;for(int i1;in;i)fac[i]fac[i-1]*i%mod;inv[n]fpow(fac[n]);for(int in;i1;i--)inv[i-1]inv[i]*i%mod;ifac[1]1;for(int i2;in;i)ifac[i]mod-ifac[mod%i]*(mod/i)%mod;
}
void dfs(int u){f[u][0]1;for(auto v:G[u]){dep[v]dep[u]1,dfs(v);memset(f[0],0,sizeof f[0]);for(int i0;idep[v];i)for(int j0;ijdep[v];j)(f[0][ij]f[u][i]*g[v][j])%mod;memcpy(f[u],f[0],sizeof f[0]);}memset(f[0],0,sizeof f[0]);for(int i0;idep[u]1;i)for(int j0;jdep[u]1;j)(f[0][j]f[u][i]*to[i][j])%mod;memset(f[u],0,sizeof f[u]);ll mul1;for(int i0;idep[u]1;i){for(int j0;ijdep[u]1;j)(f[u][ij]mul*f[0][j])%mod;mulmul*(a[u]-i)%mod*ifac[i1]%mod;}for(int i0;idep[u];i)g[u][i](f[u][i]f[u][i1])%mod;
}
signed main(){//freopen(data.in,r,stdin);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i2;in;i)cinfa[i],G[fa[i]].pb(i);cinr;init(n);to[0][0]1;for(int i1;in;i){for(int j0;ji;j){ll mul1;int sgn(i-j1)?-1:1;for(int k0;kn;k){(to[i][k]sgn*binom(i,j)*mul)%mod;mulmul*((j*r-k)%mod)%mod*ifac[k1]%mod;}}}for(int i1;in;i)cina[i];dfs(1);cout(f[1][0]mod)%mod;
}
