原題鏈接
簡要翻譯：
有一個連通圖，A和B同時從點1出發，沿不同的路徑前進，原本，圖上的每一條邊都是灰色的，A將經過的邊涂成紅色，B將經過的邊涂成藍色的，每個回合每個人只能走灰色的邊，當某個回合中不存在兩條不同的灰色路徑來同時移動A和B時，游戲結束，試求結束時，圖上邊的涂色情況有多少種?只要有一條邊顏色不同，就視為兩種情況，特別的，對圖中除點1外的點，每一個點都有且只有兩條邊與之相連，
資料范圍：
\(2\leq N\leq3e5\)，\(2\leq M\leq 2\times N\)
題解：
(說是題解，其實更像是思考程序，想直接看正解的可以下拉到我推導n個環的地方)
顯然，我們可以發現，圖中所有的環都只有點1一個公共點，或者說，這個圖是由以且只以點1為公共點的環構成的，
邊軍訓邊想想了一整天，我決定打開cf看下標簽
Divide and Conquer 分治演算法
好吧沒看懂
首先，我們先求出環的數量與每個環中點的數量，復雜度為 \(O(N)\) ，簡單的遍歷即可，
當然，你也可以一邊讀入一邊利用并查集確定除1外每個點的歸屬，然后直接統計，這樣就省去了建圖遍歷的程序，
染色部分只含有1個環時:
- 答案加 \(2\) ，(紅藍互換)
染色部分只含有2個環時:
- 若兩個環大小不同，則終點會在較大環里，且由于大小不同，終點不會將環平分，所以終點在環上會有一個對稱的位置，再加上紅藍互換，答案加 \(4\)
- 當然，記得加上含有一個環的情況，
- 此時，總答案為8，這便是樣例的情況，
- 若兩個環大小相同，則終點為1，若圖上沒有別的環了，則答案加 \(2\) ，否則答案加 \(0\) ，(因為終點為點1，但與點1相連的環還有其他的，可以繼續移動)
當含有3個環時，記這三個環的點數分別為 \(a\leq b\leq c\) ：
- 若 \(a+b=c\) ，與上面2個環的情況類似， 當終點在1時，如果只有3個環，答案加 \(2\) ，否則答案加 \(0\) ，當終點在c上時，若 \(a=b\) ，答案加 \(2\) ，否則加 \(4\) ，
- 否則若 \(a+b<c\) ，顯然終點只能出現在第三個環里，當兩個小環顏色相同，與兩個環的第一種情況同理，答案加 \(4\) ；當兩個小環顏色不同，若這兩個環大小相同，則終點平分第三個環，答案加 \(2\) ，否則，答案加 \(4\) ，
- 若 \(a+b>c\) ：
- 若 \(a=b\) ，答案加 \(2(終點在c)+4(終點在b)+4(終點在a)\)
- 若 \(a<b\) ，答案加 \(4+4+4\)
- 不難發現：當終點所在環兩側環的點數相同時，答案加 \(2\) ，否則答案加 \(4\)
對于含有n個環的情況下，記這n個環點數分別為 \(a_1\leq a_2\leq ...\leq a_n\)
- 我們將這些環分為3個部分，\(S_1,S_2,a_k\) ，注意 \(S_1,S_2\) 可以為0，我們記終點在 \(a_k\) 中，且 \(S_1\leq S_2\) ，則 \(a_k\) 可以作為終點環，當且僅當 \(S_1+a_k>S_2\) ，
- 若 \(S_1=S_2\) ，答案加 \(2\) ，否則，答案加 \(4\) ，
- 但是，這樣的組合會有很多種，列舉顯然不能解決問題，
- 若 \(S_1+a_k=S_2\) ，且沒有更多的環時，答案加 \(2\) ，否則答案加 \(0\) ，
假定我們已經求出n-1個環下的答案，現在讓我們嘗試推匯出n個環的答案
思路1：
- 對于原有的每個對答案有貢獻的情形：
- 注意，此處我們將 \(S_1+a_k=S_2\) 的情形也加入討論
- 假若我們是按大小順序加入環，對于每個 \(S_1+a_k>S_2\) 的情形，如果我們把 \(a_k\) 并入 \(S_1\) ，新環設為終點環，情況仍然是合法的，即滿足 \(S_2+a_n>(S_1+a_k)\)
- 對于 \(a_n<S_2-S_1+a_k\) 的情形，我們將新環并入 \(S_1\) 后，有 \(S_2+a_k>(S_1+a_n)\) ，情況仍然合法
- ...
- 下面不再列舉出各種情況，但是，我們不難發現，如果我們維護的是各個 \(d=S_2-S_1+a_k\) 的數量，在某些情形下，合并后，我們就無法利用 \(d\) 計算出 \(d'\) ，進而無法更新，如果維護 \(d=S_1-S_2+a_k\) ，也有類似的問題，
- 比方說，我們維護的是 \(d=S_2-S_1+a_k\) ，對于每個 \(S_1+a_k>S_2\) 的情形，我們將新環設為終點環，把 \(a_k\) 并入 \(S_1\) 之后， \(d'=(S_1+a_k)-S_2+a_n\) ，由于符號的改變，我們無法在只知道 \(d\) 的情況下推出 \(d'\)
- 而兩個同時維護，復雜度又不允許，
- 也就是說，我們需要更巧妙的維護方式，
在我們上面的分析中，我們都是整個環整個環的操作，并且根據大小關系的合法與否來實作統計和更新，擁有繁瑣的判斷程序和無法維護的弊端，那么，是否有更為通用的方法呢？
思路2(正解)：
-
我們發現，無論我們維護的 \(d\) 是怎樣的形式，\(S_1\) 與 \(S_2\) 總是相抵的，現在，我們將紅色邊的數量記為正，藍邊數量記為負，則最終我們希望二者相抵為0，
-
邊的變化有兩種方式，一是加入整個環，二是將環確認為終點環并加入環中的部分邊，
-
我們讓 \(f[i][j][0]\) 表示考慮到第i個環，邊數相抵后的值為j，0表示答案是由完整的環加減也就是還未確定終點環下得到的，1表示答案是已經確定了終點環后得到的，
-
顯然，有： \(f[i][j][0]=f[i-1][j-a_i][0]+f[i-1][j+a_i][0]+f[i-1][j][0]\)
-
接下來我們討論把當前環i作為終點環的情況
-
我們將環平分為兩個非空的部分，不難發現，以這個環為終點環后其對j值的影響如下：\(1-(a_i-1),2-(a_i-2),...,(a_i-1)-1\) 不難發現，影響是從 \(2-a_i\) 到 \(a_i-2\) 的間隔為2的數，我們記這個影響的集合為 \(D_1\)
-
應有： \(f[i][j][1]+=\sum f[i-1][p][0]\) ， \(p\in D_1\)
-
另外，別忘了統計終點環不是i但已經確定終點環的情況： \(f[i][j][1]+=f[i-1][j-a_i][1]+f[i-1][j+a_i][1]+f[i-1][j][1]\)
-
什么？你以為這樣就完了？太天真了，
-
題目可沒有保證藍色和紅色最終能到達同一個點，也就是說，可能存在這樣的情況：藍色和紅色的終點在同一個環上某條邊的兩端，
-
注意此時跟上面的情況有點區別，上面我們要求將環平分為非空的兩部分，是因為在用上了整個環的情形下，如果紅邊或藍邊的邊數為0，則終點會在1點，而由于1點的特殊性(如果你真的看了我前面的推導思路)，我們無法在此處判斷把共同終點設在1點是否合法，所以，我們要求兩部分非空，
-
但在現在，我們在環中空出了一條邊，不論兩部分是否為空，我們都能確定終點(邊)在這個環中，所以可以為空
-
此時，這個終點環對j的影響如下： \(0-(a_i-1),1-(a_i-2),...,(a_i-1)-0\),我們記這個影響的集合為 \(D_2\)
-
我們發現 \(D_1\cup D_2=[1-a_i,a_i-1]\)
-
那么我們自然而然地想到，維護f[i-1][j][0]的前綴和，然后 \(f[i][j][1]+=sum[j+a_i-1]-sum[j-a_i]\)
-
那么恭喜你，這里還有一個坑，
-
假如我們在環中空出的這條邊的一端為1點，也就是上面我們分析到的其中一部分為空的情況，需要滿足一個前提條件：用上所有的環，或著這么表述：整個圖中空下來保持褐色的，只有這條邊，因為如果還有別的環，這個環必然與1相連，那么這兩種顏色就可以從1點沿著環繼續延伸，這種情況是不合法的，
-
因此，我們在計算空出了邊且邊與1相連的情況時，有如下調整：
-
統計終點環不是i但已經確定終點環的情況時，不能加上 \(f[i-1][j][1]\) ，也就是不能不用這個環，
-
但這就與我們上面的公式相矛盾，
-
因此，我們需要將這種情況同以1為終點的情況一起拿出來單獨計算，
-
順帶一提，我們上面算的 \(f[i][j][1]\) 的終點環處經過紅藍互換后可以形成新的答案，所以最終答案要乘以2，
最后是代碼：
#include <cstdio>
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i>=b;i--)
inline char getc(){
static char buf[1<<14],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int scan(){
REG int x=0; REG char ch=0;
while(ch<48) ch=getc();
while(ch>=48) x=x*10+ch-48,ch=getc();
return x;
}
inline void swap(int &A,int &B){
REG int x=A; A=B; B=x;
}
inline int max(const int&A,const int&B){
return A>B?A:B;
}
inline int min(const int&A,const int&B){
return A<B?A:B;
}
const int MOD=1e9+7;
inline int add(int A,int B){
//if(B<0) B+=MOD
return B>MOD-A?A-MOD+B:A+B;
}
const int N=2e3+5,M=4e3+5;
int n,m,fa[N],c[N],a[N],cn,f[2][M<<1][2];
inline int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
n=scan(); m=scan();
rep(i,1,n) fa[i]=i,c[i]=1;
rep(i,1,m){
REG int u=find(scan()),v=find(scan());
if(u==1||v==1||u==v) continue;
fa[v]=u; c[u]+=c[v];
}
rep(i,2,n) if(fa[i]==i) a[++cn]=c[i]+1;
REG int zero=m+1,t=1,ans;
f[0][zero][0]=1;
for(REG int i=1;i<=cn;i++,t^=1){
//直接繼承i-1的答案，是這個環不走的情況
rep(j,1,(m<<1)+1){
f[t][j][0]=f[t^1][j][0];
f[t][j][1]=f[t^1][j][1];
}
rep(j,1,(m<<1)+1){
if(j-a[i]>0){
f[t][j][0]=add(f[t][j][0],f[t^1][j-a[i]][0]);
f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]][1]);
}
if(j+a[i]<(m+1)<<1){
f[t][j][0]=add(f[t][j][0],f[t^1][j+a[i]][0]);
f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]][1]);
}
}
rep(j,1,(m<<1)+1) f[t^1][j][0]=add(f[t^1][j][0],f[t^1][j-1][0]);
rep(j,1,(m<<1)+1){
REG int l=max(1,j-a[i]+2),r=min(j+a[i]-2,(m<<1)+1);
f[t][j][1]=add(f[t][j][1],add(f[t^1][r][0],MOD-f[t^1][l-1][0]));
}
}
//終點環內紅藍互換(或者說把環鏡像翻轉)，答案翻倍
ans=add(f[t^1][zero][1],f[t^1][zero][1]);
//printf("t1:%d\n",ans);
rep(j,1,(m<<1)+1) f[t][j][0]=f[t^1][j][0]=f[t][j][1]=f[t^1][j][1]=0;
f[t^1][zero][0]=1;
for(REG int i=1;i<=cn;i++,t^=1){
//想要以1為唯一終點或終點之一，就不能空出任何環
rep(j,1,(m<<1)+1) f[t][j][0]=f[t][j][1]=0;
rep(j,1,(m<<1)+1){
if(j-a[i]>0){
f[t][j][0]=add(f[t][j][0],f[t^1][j-a[i]][0]);
f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]][1]);
}
if(j+a[i]<(m+1)<<1){
f[t][j][0]=add(f[t][j][0],f[t^1][j+a[i]][0]);
f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]][1]);
}
//統計空出一條邊且該邊與1相連的情況
if(j-a[i]+1>0) f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]+1][0]);
if(j+a[i]-1<(m+1)<<1) f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]-1][0]);
}
}
//對于f[i][0][0]也就是以1為唯一終點的情況 紅藍的各種組合在紅正藍負相抵中已經體現了，不需要互換了，
ans=add(ans,f[t^1][zero][0]);
//printf("t2:%d\n",ans);
//對于f[i][0][1]我們鏡像翻轉 答案翻倍
ans=add(ans,add(f[t^1][zero][1],f[t^1][zero][1]));
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/142017.html
標籤：C++
上一篇：學習第41天