JSOI2019 神经网络
2022/6/13 23:20:38
本文主要是介绍JSOI2019 神经网络,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
火星人在出生后,神经网络可以看作是一个由若干无向树 \(\{T_1(V_1, E_1), T_2(V_2, E_2),\ldots T_m(V_m, E_m)\}\) 构成的森林。随着火星人年龄的增长,神经连接的数量也不断增长。初始时,神经网络中生长的连接 \(E^\ast = \varnothing\)。神经网络根据如下规则生长:
- 如果节点 \(u \in V_i, v \in V_j\) 分别属于不同的无向树 \(T_i\) 和 \(T_j\)(\(i \neq j\)),则 \(E^\ast\) 中应当包含边 \((u, v)\)。
最终,在不再有神经网络连接可能生长后,神经网络之间的节点连接可以看成是一个无向图 \(G(V,E)\),其中
\[V=V_1\cup V_2\cup \ldots \cup V_m,E=E_1\cup E_2\cup \ldots \cup E_m\cup E^\ast \]火星人的决策是通过在 \(G(V, E)\) 中建立环路完成的。针对不同的外界输入,火星人会建立不同的神经连接环路,从而做出不同的响应。为了了解火星人行为模式的复杂性,JYY 决定计算 \(G\) 中哈密顿回路的数量。
\(G(V, E)\) 的哈密顿回路是一条简单回路,从第一棵树的第一个节点出发,恰好经过 \(V\) 中的其他节点一次且仅一次,并且回到第一棵树的第一个节点。
Solution
题目限制的哈密顿回路等价于将给出的树划分成若干条链,按照任意顺序将不属于同一棵树的链连接成一张大环的方案数
这里唯一的限制就是不能让两个属于同一棵树的链在路径中相邻,这部分后面将使用容斥进行计算
首先使用树上背包计算将每棵树划分成若干条链的方案数,这里长度超过 \(1\) 的链要附加 \(2\) 的系数,因为可以双向通过
设 \(f_{i,j,0/1/2}\) 表示 \(i\) 号点的子树中划分成了 \(j\) 条链,且根在链上的度数为 \(0/1/2\) ,转移分为是否将根和当前归并的子树根所在的链连接起来,式子可以写作:
\[\begin{aligned}f_{x,i+j,k}&\leftarrow f_{x,i,k}(f_{t,j,0}+2f_{t,j,1}+f_{t,j,2})\\f_{x,i+j-1,1}&\leftarrow f_{x,i,0}(f_{t,j,0}+f_{t,j,1})\\f_{x,i+j-1,2}&\leftarrow f_{x,i,1}(f_{t,j,0}+f_{t,j,1})\end{aligned} \]这里是在每条链确定和再浅的点没有联系之后将 \(2\) 的系数附加的
尝试使用 \(\rm EGF\) 计算形成若干条链的方案数,对相邻且在同一棵树上的链进行容斥:
\[\sum_{i=1}^nf_ii!\sum_{j=0}^{i-1} (-1)^j\binom{i-1}j\frac{x^{i-j}}{(i-j)!} \]第二个求和符号中枚举有几个空隙填了相同的元素,也就是最后保留了 \(i-j\) 条链,该容斥系数的正确性可以通过简单组合恒等式得到
此时遗留问题就是第一条和最后一条链可能在同一棵树上,特殊化第一棵树的第一个点所在的链,重新给它编 \(\rm EGF\) :
由于钦定起点,那么第一棵树参与任意排列的链数减少 \(1\),写作
\[\sum_{i=1}^nf_i(i-1)!\sum_{j=1}^{i} (-1)^{i-j}\binom{i-1}{i-j}\frac{x^{j-1}}{(j-1)!} \]强制首尾的链相同的情况也是类似的,有两个链不计入最后 \(\rm EGF\) 的排列即可:
\[\sum_{i=1}^nf_i(i-1)!\sum_{j=2}^{i} (-1)^{i-j}\binom{i-1}{i-j}\frac{x^{j-2}}{(j-2)!} \]使用 \(\Theta(n^2)\) 卷积!
Code
const int N=5010; vector<int> G[N]; inline vector<int> Mul(vector<int> &a,vector<int> &b){ int n=a.size(),m=b.size(); vector<int> res(n+m-1); for(int i=0;i<n;++i) for(int j=0;j<m;++j) res[i+j]+=a[i]*b[j]%mod; for(int i=0;i<n+m-1;++i) res[i]%=mod; return res; } int C[N][N],fac[N],ifac[N],tmp[N][3]; signed main(){ C[0][0]=ifac[0]=fac[0]=1; for(int i=1;i<=5000;++i){ C[i][0]=1; fac[i]=mul(fac[i-1],i); ifac[i]=ksm(fac[i],mod-2); for(int j=1;j<=i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]); } int T; scanf("%lld",&T); vector<int> ans={1}; bool mark=0; while(T--){ int n; scanf("%lld",&n); for(int i=1;i<n;++i){ int u,v; scanf("%lld%lld",&u,&v); G[u].emplace_back(v); G[v].emplace_back(u); } vector<vector<int> >dp[3]; rep(i,0,2) dp[i].resize(n+1); vector<int> siz(n+1); function<void(int,int)>dfs=[&](int x,int fat){ siz[x]=1; int sum=1; for(auto t:G[x]) if(t!=fat) dfs(t,x),sum+=siz[t]; dp[0][x].resize(sum+1); dp[1][x].resize(sum+1); dp[2][x].resize(sum+1); dp[0][x][1]=1; for(auto t:G[x]) if(t!=fat){ for(int i=1;i<=siz[x];++i){ for(int j=1;j<=siz[t];++j){ rep(k,0,2) tmp[i+j][k]+=dp[k][x][i]*(dp[0][t][j]+2*(dp[1][t][j]+dp[2][t][j]))%mod; tmp[i+j-1][1]+=dp[0][x][i]*(dp[0][t][j]+dp[1][t][j])%mod; tmp[i+j-1][2]+=dp[1][x][i]*(dp[0][t][j]+dp[1][t][j])%mod; } } siz[x]+=siz[t]; for(int i=1;i<=siz[x];++i){ rep(j,0,2) dp[j][x][i]=tmp[i][j]%mod,tmp[i][j]=0; } } G[x].clear(); return ; }; dfs(1,0); vector<int>f(n+1),poly(n+1); for(int i=1;i<=n;++i) f[i]=(dp[0][1][i]+2*(dp[1][1][i]+dp[2][1][i]))%mod; if(!mark){ for(int i=1;i<=n;++i){ int coef=mul(fac[i-1],f[i]); for(int j=1;j<=i;++j){ if((i-j)&1) poly[j-1]-=coef*C[i-1][j-1]%mod; else poly[j-1]+=C[i-1][j-1]*coef%mod; } for(int j=2;j<=i;++j){ if((i-j)&1) poly[j-2]+=C[i-1][j-1]*coef%mod; else poly[j-2]-=C[i-1][j-1]*coef%mod; } } mark=1; }else{ for(int i=1;i<=n;++i){ int coef=mul(fac[i],f[i]); for(int j=1;j<=i;++j){ if((i-j)&1) poly[j]-=C[i-1][j-1]*coef%mod; else poly[j]+=C[i-1][j-1]*coef%mod; } } } for(int i=0;i<=n;++i){ poly[i]=(poly[i]%mod+mod)%mod; ckmul(poly[i],ifac[i]); } ans=Mul(ans,poly); } int sum=0; for(int i=1;i<ans.size();++i) sum+=ans[i]*fac[i]%mod; printf("%lld\n",sum%mod); return 0; }
这篇关于JSOI2019 神经网络的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26React入门教程:从零开始搭建你的第一个React应用
- 2024-12-25Vue2入门教程:轻松掌握前端开发基础
- 2024-12-25Vue3入门指南:快速搭建你的第一个Vue3项目
- 2024-12-25JS基础知识入门教程
- 2024-12-25React基础知识详解:从入门到初级应用
- 2024-12-25Vue3基础知识详解与实战指南
- 2024-12-25Vue3学习:从入门到初步掌握
- 2024-12-25Vue3入门:新手必读的简单教程
- 2024-12-23【JS逆向百例】爱疯官网登录逆向分析
- 2024-12-21Vue3教程:新手入门到实践应用