2018.07.13 [HNOI2015]落忆枫音（容斥原理+dp）

洛谷的传送门

 bzoj的传送门

题意简述：在DAG中增加一条有向边，然后询问新图中一共有多少个不同的子图为“树形图”。

解法：容斥原理＋dp，先考虑没有环的情况，经过尝试不难发现总的有向树个数就等于所有点的度数的乘积。而现在有了环，显然我们应该减去算多了的值。这样的话只需要简单的容斥原理就行了。

代码如下:

#include<bits/stdc++.h>
#define mod 1000000007
#define N 200005
#define M 400005
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    return ans;
}
ll n,m,x,y,tot=0,first[N];
ll ans=1,mul=1,dp[N],du[N];
bool vis[N];
struct Node{ll v,next;}e[M];
inline void add(ll u,ll v){e[++tot].v=v,e[tot].next=first[u],first[u]=tot,++du[u];}
inline ll ksm(ll x,ll p){
    ll ret=1;
    while(p){
        if(p&1)ret=ret*x%mod;
        x=x*x%mod,p>>=1;
    }
    return ret;
}
inline void dfs(ll p){
    if(vis[p])return;
    vis[p]=true;
    if(p==y){dp[p]=mul*ksm(du[p],mod-2)%mod;return;}
    for(ll i=first[p];i;i=e[i].next){
        dfs(e[i].v),dp[p]+=dp[e[i].v],dp[p]%=mod;
    }
    dp[p]=(dp[p]*ksm(du[p],mod-2))%mod;
}
int main(){
    memset(vis,false,sizeof(vis));
    n=read(),m=read(),x=read(),y=read();
    for(ll i=1;i<=m;++i){ll u=read(),v=read();add(v,u);}
    du[1]=1;
    for(ll i=1;i<=n;++i){
        if(i==y)ans*=(du[i]+1),ans%=mod;
        else ans*=du[i],ans%=mod;
        mul*=du[i],mul%=mod;
    }
    dfs(x);
    ans-=dp[x];
    if(ans<0)ans+=mod;
    printf("%lld",ans);
    return 0;
}

巴特西

2018.07.13 [HNOI2015]落忆枫音（容斥原理+dp）

最新文章

热门文章