首页 > 代码库 > BZOJ 4013 【HNOI2015】 实验比较
BZOJ 4013 【HNOI2015】 实验比较
题目链接：实验比较
如果我们把相等关系全部缩起来的话，这道题给出的小于关系如果有环，那么就是不合法的，否则就构成了一片森林。
定义等于号连起来的所有变量看做一个块。
然后我们就可以令\(f_{i,j}\)表示以\(i\)为根的子树中分成了\(j\)个块的方案数。如果我们在给森林添加一个虚根，把它变成一棵树的话，最终的答案就很好算了。
然后我们考虑一下如何转移。设\(v\)是\(u\)的子节点，那么\(f_{u,i}\)和\(f_{v,j}\)可以转移到\(f_{u,k}(\max(i,j)\le k \le i+j)\)。具体转移的式子为：
\[f_{u,k}=f_{u,i}f_{v,j}\binom{k}{i}\binom{i}{j-(k-i)}\]
可以看成\(i\)个块先占了\(i\)个地方，然后\(v\)子树的\(j\)个块先把空余的位置占满，再随便找位置合并。注意转移的时候不要把需要用的信息给覆盖了，需要用一个数组来辅助转移。
由于根节点不能和子树内任意一个节点相同，所以最后再把根节点加入到\(dp\)值中即可。注意虚根需要特判一下。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define mod 1000000007
#define maxn 100010
#define maxm 400010
using namespace std;
typedef long long llg;
int n,m,du[maxn];
int head[maxn],next[maxm],to[maxm],tt;
llg f[maxn],ans;
bool vis[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();
if(c==‘-‘) c=getchar(),q=1;
while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();
return q?-w:w;
}
void gi(llg &x){if(x>=mod) x%=mod;}
llg mi(llg a,int b){
llg s=1;
while(b){
if(b&1) s=s*a,gi(s);
a=a*a,gi(a); b>>=1;
}
return s;
}
llg dfs(int u){
if(vis[u]) return f[u]; vis[u]=1;
for(int i=head[u];i;i=next[i])
f[u]+=dfs(to[i]),gi(f[u]);
f[u]*=mi(du[u],mod-2);
gi(f[u]); return f[u];
}
int main(){
File("maple");
n=getint(); m=getint();
int x=getint(),y=getint();
while(m--){
int u=getint(),v=getint(); du[v]++;
to[++tt]=v;next[tt]=head[u];head[u]=tt;
}
du[y]++; ans=1;
for(int i=2;i<=n;i++) ans*=du[i],gi(ans);
if(y!=1 && x!=1){
vis[x]=1; f[x]=ans*mi(du[x],mod-2);
gi(f[x]); ans-=dfs(y);
ans%=mod; if(ans<0) ans+=mod;
}
printf("%lld\n",ans);
return 0;
}
BZOJ 4013 【HNOI2015】 实验比较
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。