組合計數的一道好題。什么非主流題目

題目背景

（背景冗長請到題目頁面查看）

題目描述

不妨假設楓葉上有 \(n?\) 個穴位，穴位的編號為 \(1\sim n?\)。有若干條有向的脈絡連接著這些穴位。穴位和脈絡組成一個有向無環圖——稱之為脈絡圖（例如圖 1），穴位的編號使得穴位 \(1?\) 沒有從其他穴位連向它的脈絡，即穴位 1 只有連出去的脈絡；由上面的故事可知，這個有向無環圖存在一個樹形子圖，它是以穴位 \(1?\) 為根的包含全部 \(n?\) 個穴位的一棵樹——稱之為脈絡樹（例如圖 2 和圖 3 給出的樹都是圖 1 給出的脈絡圖的子圖）；值得注意的是，脈絡圖中的脈絡樹方案可能有多種可能性，例如圖 2 和圖 3 就是圖 1 給出的脈絡圖的兩個脈絡樹方案。

脈絡樹的形式化定義為：以穴位 \(r\) 為根的脈絡樹由楓葉上全部 \(n\) 個穴位以及 \(n-1\) 條脈絡組成，脈絡樹里沒有環，亦不存在從一個穴位連向自身的脈絡，且對于楓葉上的每個穴位 \(s\)，都存在一條唯一的包含于脈絡樹內的脈絡路徑，使得從穴位 \(r\) 出發沿著這條路徑可以到達穴位 \(s\)。

現在向脈絡圖添加一條與已有脈絡不同的脈絡（注意：連接 \(2\) 個穴位但方向不同的脈絡是不同的脈絡，例如從穴位 \(3\) 到 \(4\) 的脈絡與從 \(4\) 到 \(3\) 的脈絡是不同的脈絡，因此，圖 1 中不能添加從 \(3\) 到 \(4\) 的脈絡，但可添加從 \(4\) 到 \(3\) 的脈絡），這條新脈絡可以是從一個穴位連向自身的（例如，圖 1 中可添加從 \(4\) 到 \(4\) 的脈絡）。原脈絡圖添加這條新脈絡后得到的新脈絡圖可能會出現脈絡構成的環。

請你求出添加了這一條脈絡之后的新脈絡圖的以穴位 \(1\) 為根的脈絡樹方案數。

由于方案可能有太多太多，請輸出方案數對 \(1000000007\) 取模得到的結果。

輸入格式

輸入文件的第一行包含四個整數 \(n\)、\(m\)、\(x\) 和 \(y\)，依次代表楓葉上的穴位數、脈絡數，以及要添加的脈絡是從穴位 \(x\) 連向穴位 \(y\) 的。

接下來 \(m\) 行，每行兩個整數，由空格隔開，代表一條脈絡。第 \(i\) 行的兩個整數為 \(u_i\) 和 \(v_i\)，代表第 \(i\) 條脈絡是從穴位 \(u_i\) 連向穴位 \(v_i\) 的。

輸出格式

輸出一行，為添加了從穴位 \(x\) 連向穴位 \(y\) 的脈絡后，楓葉上以穴位 \(1\) 為根的脈絡樹的方案數對 \(1000000007\) 取模得到的結果。

輸入輸出樣例

輸入樣例：

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

輸出樣例：

3

數據范圍與約定

對于所有測試數據，\(1\leq n\leq 100000, \ n-1 \leq m \leq \min \left(200000, \frac{n(n - 1)}{2}\right), \ 1 \leq x, y, u_i, v_i \leq n?\)。

題解：

首先需要找出一個不需要拓撲排序就能解決不加邊時的脈絡樹數量的方法。

對于每個點 \(u(u\ge 2)\) ，假定它的入度為 \(d_i\) ，則它有 \(d_i\) 個父親可供選擇。我們只需要從上往下看，就可以發現每一層都是互相獨立的，因此加邊之前脈絡樹的數量為
\[ \prod_{i=2}^nd_i \]
此時考慮加邊。正常情況下按上面的方式計數，邊數為 \(n-1\) 的圖的總數 \(sum\) 為
\[ sum=\prod_{i=2}^n\left(d_i+[i=y]\right) \]
但是實際上不是所有 \(sum\) 種方案都符合題意，由于每個點選擇父親是自由從入邊選的，因此可能存在環，此時就不滿足”脈絡樹“的定義了，而且圖/樹也沒有明顯分層。

我們考慮所有的 \(sum?\) 種方案，從中減掉包含環的那些方案。由于我們加入的邊是 \(\left<x,y\right>?\)，所以一定是與路徑 \(y\to x?\) 成環。因此我們只需要排除那些包含 \(y\to x\) 的路徑的邊數為 \(n-1?\) 的圖就可以了。

注意由于加了新邊之后的圖只有一個環，因此 \(n-1?\) 條邊的圖也最多只有一個環。

話再說回來，包含 \(y\to x?\) 的路徑的圖我們可以認為這條路徑上的所有點（包括 \(x,y?\)）都被欽定了一個父親（其中 \(x?\) 的父親認為是 \(y?\)，因為要成環）。假設用 \(S=\left\{a_i\right\}?\) 表示這條路徑，那么包含 \(y\to x?\) 的圖種類數就是 \(\prod_{i\notin S}d_i?\)。

而最終的答案就是 \(sum-\sum_{S:y\to x}\prod_{i\notin S}d_i?\)。

此時考慮如何求出所有的 \(y\to x\)。可以建立原圖的反向邊，跑拓撲排序。設定狀態 \(f_k\) 表示 \(\sum_{S:k\to x}\prod_{i\notin S}d_i\)，每次從原圖的邊 \(\left<u,v\right>\) 轉移時，即欽定了 \(v\) 的入邊，所以狀態轉移方程為
\[ f_u=\sum_{\left<u,v\right>\in E}\frac{f_v}{d_v} \]
由于我們還要欽定 \(x\) 的入邊是 \(y\)，因此最終的答案是
\[ ans=sum-\frac{f_x}{d_x} \]
時間復雜度為 \(O(n)\) 或 \(O(n\log n)\) （在線求逆元）

Code：

#include<cstdio> #include<cstring> #define p 1000000007 int Plus(int x,int y) {return (x+y>=p)?(x+y-p):(x+y);} int Mul(int x,int y) {return 1ll*x*y%p;} struct edge {int n,nxt;edge(int n,int nxt){this->n=n;this->nxt=nxt;}edge(){} }e[200000]; int head[100100],ecnt=-1; void add(int from,int to) {e[++ecnt]=edge(to,head[from]);head[from]=ecnt; } int d[100100],in[100100]; //d表示真實入度 in表示拓撲排序中的入度 int q[100100],l=0,r=0; int f[100100],inv[100100]; int main() {memset(head,-1,sizeof(head));inv[1]=1;for(int i=2;i<=100000;++i)inv[i]=Mul(p-p/i,inv[p%i]);int n,m,x,y,u,v;scanf("%d%d%d%d",&n,&m,&x,&y);for(int i=1;i<=m;++i){scanf("%d%d",&u,&v);add(v,u);++in[u];++d[v];}f[x]=1;int sum=1;for(int i=2;i<=n;++i){if(!in[i])q[++r]=i;f[x]=Mul(f[x],d[i]);sum=Mul(sum,d[i]+(i==y));}if(y==1){printf("%d\n",sum);return 0;}while(l<r){int k=q[++l];for(int i=head[k];~i;i=e[i].nxt){--in[e[i].n];f[e[i].n]=Plus(f[e[i].n],Mul(f[k],inv[d[k]]));if(!in[e[i].n])q[++r]=e[i].n;}}printf("%d\n",Plus(sum,p-Mul(f[y],inv[d[y]])));return 0; }

轉載于:https://www.cnblogs.com/wjyyy/p/lg3244.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的洛谷 P3244 / loj 2115 [HNOI2015] 落忆枫音 题解【拓扑排序】【组合】【逆元】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。