NOI 2008 設計路線 design

本文正體字版由OpenCC轉換

基本方法

首先，注意一個重要的條件“每個城市最多隻和一個位於它東邊的城市相連”，通過這個條件，必須能夠明白這個國家的公路網其實是樹（或森林）。爲什麼是樹？我們知道，樹中除了根其餘節點都有且只有一個父節點，假設每個城市東邊的城市就是它的父節點，恰好滿足是樹的條件。把城市1當作根節點，如果每個節點都有到達根節點1的路徑，那麼肯定只有一棵樹，如果圖中有多個連通分量，那麼是無解的，輸出兩個-1。另外對於這道題，由於數據可以保證不存在環，只需判斷M是否爲N-1即可。

明白這是一棵樹以後，問題就清晰多了。問題可以被描述爲：給定一個根節點爲1的數要求在樹中找到一些不相交的鏈，使得每個節點的不便利值的最大值最小，並求出滿足條件的方案個數。一個節點的不便利值就是從該節點到根的路徑上經過的非鏈邊的條數。

先考慮第一問，求最小不便利值。在紙上隨意畫幾棵樹，算出最小不便利值，可以發現很難使最小不便利值很大。當根節點至少有三個子節點時，才能使不便利值爲1，而第二層的節點再都至少有三個子節點，才能使不便利值爲2。可以發現，只有節點個數至少爲一個高度爲k+1的滿三叉樹，才能使不便利值達到k，反證法很容易證明。對於最大的數據N<=100000，也不過最多可能有10層滿三叉樹，最大達到的不便利值爲9。發現第一問的可能值很少，可以考慮和第二問共同解決。可以知道，使得方案數大於0的最小不便利值B，一定爲結果。於是可以從0開始枚舉第一問的答案，計算方案數，直到方案數大於0。

解決第二問，需要用到樹形動態規劃。考慮每個子樹根節點向下連邊構造不相交鏈，它向下連邊有3種可能，不連邊，只連一條邊，只連兩條邊。不可能連更多，否則就會出現相交的鏈，連兩條邊還必須滿足它的父節點沒有向它連邊。據此定義：

F[i,b]爲以i爲根的子樹中，每個節點相對於子樹的根最大不便利值不超過b，且子樹根節點向下連兩條邊的方案個數。
G[i,b]爲以i爲根的子樹中，每個節點相對於子樹的根最大不便利值不超過b，且子樹根節點向下連一條邊或不連邊的方案個數。
對於F[i,b] (b>0)
- 當i有1個或0個子節點
- F[i,b]=0
當i有至少2個子節點
- F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l爲i的不同的子節點)
對於G[i,b] (b>0)
- 當i有0個子節點
- G[i,b]=1
當i有至少1個子節點
- G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l爲i的不同的子節點)

特殊地，當b爲0時

對於F[i,b]
- 當i有且只有2個子節點
- F[i,b]=G[j,b]*G[k,b] (j和k爲i的不同的子節點)
當i有多於或少於2個子節點
- F[i,b]=0
對於G[i,b]
- 當i沒有子節點
- G[i,b]=1
當i有且只有1個子節點
- G[i,b]=G[j,b] (j爲i的子節點)
當i有多餘1個子節點
- G[i,b]=0

時間複雜度爲O(N^3logN)。根據上述所有的方程，直接進行樹形動態規劃，可以拿到40~50分。觀察N的範圍(N<=100000)，要想全部通過，必須優化到O(NlogN)，向着這個目標，開始着手優化。

狀態轉移優化

F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l爲i的不同的子節點)
G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l爲i的不同的子節點)

再次觀察上述兩個方程，發現大部分時間浪費在這裏，尤其是Π(F[l,b-1]+G[l,b-1])，重複計算了很多次。是否可以把它先計算出呢？我的第一想法就是設置一個變量記錄，令W=Π(F[l,b-1]+G[l,b-1]) (l爲i的所以子節點)。在計算G[i,b]的Σ內部時，由於每次Π(F[l,b-1]+G[l,b-1])都少乘一個(F[j,b-1]+G[j,b- 1])，而多乘一個G[j,b]，結果是W/(F[j,b-1]+G[j,b-1])*G[j,b]。但這種想法是錯誤的，首先(F[j,b- 1]+G[j,b-1])可能爲0，除法不可用，就算不爲0，由於結果要求一個mod Q以後的值，除法會破壞同餘的性質。由於式子龐大而繁雜，不利於思考，我把它變換形式後思考。

對於給定的i,b，設節點i有V個子節點，定義

A[i]=F[j,b-1]+G[j,b-1] (j爲節點i的子節點 A[i]爲一個連續的數組 (1<=i<=V) )
B[i]=G[j,b] (j,k爲節點i的兩個不同子節點 B[i]爲一個連續的數組 (1<=i<=V) )
R0=Π(A[i]) (1<=i<=V)
R1=Σ(B[i]*Π(A[j])) (1<=i,j<=V ,i!=j)
R2=Σ(B[i]*B[j]*Π(A[k])) (1<=i,j,k<=V ,i!=j ,i!=k ,j!=k)

則F[i,b]=R2，G[i,b]=R0+R1

我們的目的是要在線性的時間內求出R0,R1,R2，需要定義輔助的線性表。

設sf[i]爲A[i]的從第i項開始的後綴之積，則有
- sf[V]=A[V]
sf[i]=sf[i+1]*A[i] (1<=i<=V-1)
設pf[i]爲A[i]的以第i項爲尾的前綴之積，則有
- pf[0]=1
pf[i]=pf[i-1]*A[i] (1<=i<=V)

顯然，R0=pf[V]。求R1線性時間的方法不難想到，R1就是表A中去除第i個元素換成B[i]的所有的和，對於一個給定的i，只需加上 pf[i-1]*B[i]*sf[i+1]，就可以實現線性時間的求和。而求R2看似與求R1類似，卻要取出兩個元素替換，不易想出線性時間的方法。由於要取兩個元素，考慮固定第一個位置，第二個元素位置變化的和就與求R1類似了。

定義C[i]爲以第i項爲開頭的所有替換的後綴積之和。

定義式爲 C[i]=Σ(B[j]*Π(A[k])) (1<=i,j,k<=C ,i<=j,i<=k,j!=k)

爲了快速求出所有C[i]，發現C[i]與C[i+1]之間有遞推關係

C[V]=B[V]
C[i]=C[i+1]*A[i] + B[i]*sf[i+1]

於是可以在線性時間內求出了C。同時很方便，R1=C[1]。

R2=Σ(pf[i-1]*B[i]*C[i+1]) (1<=i<=N-1)，也可以在線性時間內求出了。

經過上述優化，每次狀態轉移就成了O(V)，而每個節點被訪問一次，所以總的時間複雜度爲O(N*logN)，理論上可以拿到滿分了。但是還有一下細節不容忽視，如果方案數不爲0，而Mod Q以後恰爲0了，此時枚舉應該中止了，但卻沒有，怎麼辦。我的方法是增設了兩個數組，記錄F[i,b]和G[i,b]的每項是否爲“真正的0”(區別於 mod以後的0)，在狀態轉移的處理中較爲麻煩，但是可以判斷了。

這是NOI2008相對較簡單的一道題了，NOI上有6位大牛拿到了滿分，而且平均分高達21.122。但是對於包括我在內的大多數人來說，做出這道題依然很不容易。

/* 
 * Problem: NOI2008 design
 * Author: Guo Jiabao
 * Time: 2009.3.4 22:18
 * State: Solved
 * Memo: 樹形動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=100001,MAXD=10;
typedef long long big;
using namespace std;
struct edge
{
	edge *next;
	int t;
}ES[MAXN*2];
struct vertex
{
	edge *f;
	int cnt;
}V[MAXN];
int N,M,MOD,MinB=-1,Total=-1,EC=-1;
big F[MAXN][MAXD],G[MAXN][MAXD];
big A[MAXN],B[MAXN],pf[MAXN],sf[MAXN],C[MAXN];
big R0,R1,R2;
bool ZF[MAXN][MAXD],ZG[MAXN][MAXD],ZA[MAXN],ZB[MAXN],ZC[MAXN],Zsf[MAXN],Zpf[MAXN],ZR0,ZR1,ZR2;
void dp(int i,int b);
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a].f;
	(V[a].f=&ES[EC])->t=b;
	V[a].cnt++;
}
void maketree(int i,int f)
{
	edge *k,*p;
	if (V[i].f->t==f)
		V[i].f=V[i].f->next,V[i].cnt--;
	for (k=V[i].f;k;p=k,k=k->next)
		if (k->t==f)
			p->next=k->next,V[i].cnt--;
		else
			maketree(k->t,i);
}
bool init()
{
	freopen("design.in","r",stdin);
	freopen("design.out","w",stdout);
	scanf("%d%d%d",&N,&M,&MOD);
	if (M!=N-1) return false;
	for (int i=1;i<=M;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b); addedge(b,a);
	}
	maketree(1,0);
	return true;
}
void clear()
{
	for (int i=1;i<=N;i++)
		for (int j=0;j<MAXD;j++)
			F[i][j]=G[i][j]=-1;
}
void cFG(int i,int b,big F[][MAXD],big G[][MAXD],int MOD)
{
	int j,cnt;
	edge *e;
	ZR0=false;
	for (cnt=0,e=V[i].f;e;e=e->next)
	{
		j=e->t;
		A[++cnt]=F[j][b-1]+G[j][b-1]%MOD;
		ZA[cnt]=ZF[j][b-1]&&ZG[j][b-1];
		ZR0|=ZA[cnt];
		B[cnt]=G[j][b];
		ZB[cnt]=ZG[j][b];
	}
	pf[0]=1;
	Zpf[0]=false;
	for (j=1;j<=cnt;j++)
	{
		pf[j]=pf[j-1]*A[j]%MOD;
		Zpf[j]=Zpf[j-1]||ZA[j];
	}
	R0=pf[cnt];
	sf[cnt]=A[cnt];
	Zsf[cnt]=ZA[cnt];
	for (j=cnt-1;j>=1;j--)
	{
		sf[j]=sf[j+1]*A[j]%MOD;
		Zsf[j]=Zsf[j+1]||ZA[j];
	}
	C[cnt]=B[cnt];
	ZC[cnt]=ZB[cnt];
	for (j=cnt-1;j>=1;j--)
	{
		C[j]=(C[j+1]*A[j]%MOD + B[j]*sf[j+1]%MOD)%MOD;
		ZC[j]=(ZC[j+1]||ZA[j] && B[j]||sf[j+1]);
	}
	R1=C[1];R2=0;
	ZR1=ZC[1];
	ZR2=true;
	for (j=1;j<cnt;j++)
	{
		R2+=((pf[j-1]*B[j])%MOD*C[j+1])%MOD;
		R2%=MOD;
		ZR2&=(Zpf[j-1] || ZB[j] || ZC[j+1]);
	}
}
void prepare(int i,int b)
{
	int l;
	edge *e;
	for (e=V[i].f;e;e=e->next)
	{
		l=e->t;
		if (F[l][b-1]==-1) dp(l,b-1);
		if (F[l][b]==-1) dp(l,b);
	}
}
void dp(int i,int b)
{
	int j,k;
	if (b==0)
	{
		if (V[i].cnt==2)
		{
			j=V[i].f->t;k=V[i].f->next->t;
			if (G[j][b]==-1) dp(j,b);
			if (G[k][b]==-1) dp(k,b);
			F[i][b]=G[j][b]*G[k][b]%MOD;
			ZF[i][b]=ZG[j][b]||G[k][b];
		}
		else
		{
			F[i][b]=0;
			ZF[i][b]=true;
		}
		if (V[i].cnt==1)
		{
			j=V[i].f->t;
			if (G[j][b]==-1) dp(j,b);
			G[i][b]=G[j][b];
			ZG[i][b]=ZG[j][b];
		}
		else if (V[i].cnt==0)
			G[i][b]=1;
		else
		{
			G[i][b]=0;
			ZG[i][b]=true;
		}
	}
	else
	{
		if (V[i].cnt==0)
			G[i][b]=1;
		else
			prepare(i,b);
		cFG(i,b,F,G,MOD);
		if (V[i].cnt<=1)
		{
			F[i][b]=0;
			ZF[i][b]=true;
		}
		else
		{
			F[i][b]=R2;
			ZF[i][b]=ZR2;
		}
		if (V[i].cnt>0)
		{
			G[i][b]=(R0+R1)%MOD;
			ZG[i][b]=ZR0 && ZR1;
		}
	}

}
void solve()
{
	clear();
	for (MinB=0;;MinB++)
	{
		dp(1,MinB);
		int t1=(F[1][MinB] + G[1][MinB])%MOD;
		if (t1==0 && ZF[1][MinB] && ZG[1][MinB]) continue;
		Total=t1;
		return;
	}
}
int main()
{
	if (init())
		solve();
	printf("%dn%dn",MinB,Total);
	return 0;
}

<div class="MainText">

【問題描述】

Z 國坐落於遙遠而又神奇的東方半島上，在小Z 的統治時代公路成爲這裏主要的交通手段。Z 國共有n 座城市，一些城市之間由雙向的公路所連接。非常神奇的是Z 國的每個城市所處的經度都不相同，並且最多隻和一個位於它東邊的城市直接通過公路相連。Z 國的首都是Z 國政治經濟文化旅遊的中心，每天都有成千上萬的人從Z 國的其他城市湧向首都。

爲了使Z 國的交通更加便利順暢，小Z 決定在Z 國的公路系統中確定若干條規劃路線，將其中的公路全部改建爲鐵路。

我們定義每條規劃路線爲一個長度大於1 的城市序列，每個城市在該序列中最多出現一次，序列中相鄰的城市之間由公路直接相連(待改建爲鐵路)。並且，每個城市最多隻能出現在一條規劃路線中，也就是說，任意兩條規劃路線不能有公共部分。

當然在一般情況下是不可能將所有的公路修建爲鐵路的，因此從有些城市出發去往首都依然需要通過乘坐長途汽車，而長途汽車只往返於公路連接的相鄰的城市之間，因此從某個城市出發可能需要不斷地換乘長途汽車和火車才能到達首都。

我們定義一個城市的“不便利值”爲從它出發到首都需要乘坐的長途汽車的次數，而Z 國的交通系統的“不便利值”爲所有城市的不便利值的最大值，很明顯首都的“不便利值”爲0。小Z 想知道如何確定規劃路線修建鐵路使得Z 國的交通系統的“不便利值”最小，以及有多少種不同的規劃路線的選擇方案使得“不便利值”達到最小。當然方案總數可能非常大，小Z 只關心這個天文數字mod Q 後的值。

注意：規劃路線1-2-3 和規劃路線3-2-1 是等價的，即將一條規劃路線翻轉依然認爲是等價的。兩個方案不同當且僅當其中一個方案中存在一條規劃路線不屬於另一個方案。

【輸入格式】

輸入文件第一行包含三個正整數N、M、Q，其中N 表示城市個數，M 表示公路總數，N 個城市從1~N 編號，其中編號爲1 的是首都。Q 表示上文提到的設計路線的方法總數的模數。接下來M 行，每行兩個不同的正數ai、bi (1≤ ai , bi ≤ N)表示有一條公路連接城市ai 和城市bi。 輸入數據保證一條公路只出現一次。

【輸出格式】

輸出文件應包含兩行。第一行爲一個整數，表示最小的“不便利值”。 第二行爲一個整數，表示使“不便利值”達到最小時不同的設計路線的方法總數 mod Q 的值。
如果某個城市無法到達首都，則輸出兩行-1。

【輸入樣例】

5 4 100
1 2
4 5
1 3
4 1
【輸出樣例】
1
10
【樣例說明】
以下樣例中是10 種設計路線的方法：
(1) 4-5
(2) 1-4-5
(3) 4-5, 1-2
(4) 4-5, 1-3
(5) 4-5, 2-1-3
(6) 2-1-4-5
(7) 3-1-4-5
(8) 1-4
(9) 2-1-4
(10) 3-1-4
【數據規模和約定】
對於20%的數據，滿足N,M ≤ 10。
對於50%的數據，滿足N,M ≤ 200。
對於60%的數據，滿足N,M ≤ 5000。
對於100%的數據，滿足1 ≤ N,M ≤ 100000，1 ≤ Q ≤ 120000000。</div>

上次修改時間 2017-02-03

基本方法

狀態轉移優化

相關日誌