【BZOJ】【4011】【HNOI2015】落忆枫音

时间：2022-03-13 22:24:55

拓扑排序+DP

　　题解：http://blog.csdn.net/PoPoQQQ/article/details/45194103

　　　　　　http://www.cnblogs.com/mmlz/p/4448742.html

　　通过转化……路径外的$degree_i$的乘积转化成所有点的degree之积除以路径内的，所以用到逆元……

　　PoPoQQQ的线性筛逆元好神奇啊……>_< OrzOrz

 /**************************************************************

     Problem: 4011

     User: Tunix

     Language: C++

     Result: Accepted

     Time:784 ms

     Memory:10648 kb

 ****************************************************************/

 //Huce #7 A

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,P=1e9+,INF=~0u>>;

 /*******************template********************/

 int to[N<<],next[N<<],head[N],cnt;

 void add(int x,int y){

     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;

 }

 int n,m,s,t,du[N],in[N];

 LL inv[N],f[N],ans=;

 void Linear_Shaker(){

     int i;

     for(inv[]=,i=;i<=m+;i++)

         inv[i]=(P-P/i)*inv[P%i]%P;

 }

 int Q[N];

 void tpsort(){

     int l=,r=-;

     f[t]=ans;

     F(i,,n) if (!du[i]) Q[++r]=i;

     while(l<=r){

         int x=Q[l++];

         f[x]=(f[x]*inv[du[x]])%P;

         for(int i=head[x];i;i=next[i]){

             (f[to[i]]+=f[x])%=P;

             if (!--in[to[i]]) Q[++r]=to[i];

         }

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("A.in","r",stdin);

 //  freopen("output.txt","w",stdout);

 #endif

     n=getint(); m=getint(); s=getint(); t=getint();

     Linear_Shaker();

     int x,y;

     F(i,,m){

         x=getint(); y=getint();

         add(x,y);

         in[y]++; du[y]++;

     }

     du[t]++;

     F(i,,n) ans=(ans*du[i])%P;

     if (t==){

         printf("%lld\n",ans);

     }else{

         tpsort();

         printf("%lld\n",(ans-f[s]+P)%P);

     }

     return ;

 }

4011: [HNOI2015]落忆枫音

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 133  Solved: 64
[Submit][Status][Discuss]

Description

【问题描述】 
不妨假设枫叶上有 n个穴位，穴位的编号为 1 ~  n。有若干条有向的脉络连接
着这些穴位。穴位和脉络组成一个有向无环图——称之为脉络图（例如图 1），穴
位的编号使得穴位 1 没有从其他穴位连向它的脉络，即穴位 1 只有连出去的脉络；
由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 1为根的包含
全部n个穴位的一棵树——称之为脉络树（例如图 2和图 3给出的树都是图1给出
的脉络图的子图）；值得注意的是，脉络图中的脉络树方案可能有多种可能性，例
如图2和图 3就是图 1给出的脉络图的两个脉络树方案。 
       【BZOJ】【4011】【HNOI2015】落忆枫音
脉络树的形式化定义为：以穴位 r 为根的脉络树由枫叶上全部 n个穴位以及 n
-  1 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于
枫叶上的每个穴位 s，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位
r 出发沿着这条路径可以到达穴位 s。 
现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 2个穴位但方向不
同的脉络是不同的脉络，例如从穴位3到4的脉络与从4到3的脉络是不同的脉络，
因此，图 1 中不能添加从 3 到 4 的脉络，但可添加从 4 到 3 的脉络），这条新脉络
可以是从一个穴位连向自身的（例如，图 1 中可添加从 4 到 4 的脉络）。原脉络图
添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。 
请你求出添加了这一条脉络之后的新脉络图的以穴位 1 为根的脉络树方案数。
由于方案可能有太多太多，请输出方案数对 1,000,000,007 取模得到的结果。 

Input

输入文件的第一行包含四个整数 n、m、x和y，依次代表枫叶上的穴位数、脉

络数，以及要添加的脉络是从穴位 x连向穴位y的。 
接下来 m行，每行两个整数，由空格隔开，代表一条脉络。第 i 行的两个整数
为ui和vi，代表第 i 条脉络是从穴位 ui连向穴位vi的。 

Output

输出一行，为添加了从穴位 x连向穴位 y的脉络后，枫叶上以穴位 1 为根的脉

络树的方案数对 1,000,000,007取模得到的结果。 

Sample Input

4 4 4 3
1 2
1 3
2 4
3 2

Sample Output

3

HINT

对于所有测试数据，1 <= n <= 100000，n - 1 <= m <= min(200000, n(n – 1) / 2)，

1 <= x, y, ui, vi <= n。

Source

[Submit][Status][Discuss]

相关文章