彩票计划网站开发,WordPress修改分类id,佳天下装饰公司怎么样,如何建立公司网址正题
题目链接:https://www.luogu.com.cn/problem/P3244 题目大意
给出一个DAG\text{DAG}DAG#xff0c;保证111可以到达所有点。然后再加入一条边#xff08;之后不一定是DAG\text{DAG}DAG#xff09;。
求有多少棵以111为根的外向生成树。 1≤n≤105,1≤m≤21051\leq n…正题
题目链接:https://www.luogu.com.cn/problem/P3244 题目大意
给出一个DAG\text{DAG}DAG保证111可以到达所有点。然后再加入一条边之后不一定是DAG\text{DAG}DAG。
求有多少棵以111为根的外向生成树。
1≤n≤105,1≤m≤2×1051\leq n\leq 10^5,1\leq m\leq 2\times 10^51≤n≤105,1≤m≤2×105 解题思路
发现不考虑加边都不会做/kk
其实结论不难想也很显然就是除了一号点以外所有点的入度乘积每个点选择一个父亲因为是DAG\text{DAG}DAG所以一定没有环
然后加一条边怎么搞因为可能会生成环。
可以考虑直接减去环的方案设deldeldel表示加边前的总方案那么对于每个环上所有点的度数乘积kkk需要减去的方案就是delk\frac{del}{k}kdel。
现在考虑如何计算所有点的度数乘积的倒数和。
不难搞直接DAGdp\text{DAGdp}DAGdp或者记亿化dpdpdp随便搞搞都可以
时间复杂度O(nm)O(nm)O(nm)如果线性预处理了逆元的话 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510,P1e97;
struct node{ll to,next;
}a[N1];
ll n,m,u,v,tot,ls[N],deg[N],g[N];
bool vis[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x){if(vis[x])return;vis[x]1;if(xu){g[x]power(deg[x],P-2)%P;return;}for(ll ils[x];i;ia[i].next)dfs(a[i].to),(g[x]g[a[i].to])%P;g[x]g[x]*power(deg[x],P-2)%P;
}
signed main()
{scanf(%lld%lld%lld%lld,n,m,u,v);for(ll i1;im;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);deg[y];}deg[1];ll ans1,del1;for(ll i1;in;i)ansans*(deg[i](iv))%P,deldel*deg[i]%P;dfs(v);printf(%lld\n,(ans-g[v]*del%PP)%P);
}
