動態(tài)規(guī)劃題單3

三

從這個題單開始將用 $a_{i,j}$ 而不是 $a[i][j]$ 來表示數(shù)組。

61.[CEOI2020] 星際迷航

當 $D=0$ 時，我們思考怎么求出艦長是否必勝：
因為我們只能從 $1$ 出發(fā)，所以如果我們以 $1$ 為根，我們肯定只能一直往下走。
所以可以樹形 DP，設(shè) $p_i$ 表示 $i$ 點是否為先手必勝點 (下面簡稱為必勝點，必敗點同理)。
根據(jù) SG 函數(shù)的相關(guān)知識 $p_i=mex_{j \in son(i)}$。
最后就是看 $p_1$ 是否為 true。

當 $D=1$ 時：
我們需要把第二棵樹的一個點 $y$ 接到第一棵樹的一個點 $x$ 下，所以如果我們選擇走 $(x,y)$ 這條星門，那么走到第二棵樹后就是以 $y$ 為根了，所以我們還需要求出以每一個點為根時，$p$ 數(shù)組的情況，我們先假設(shè)我們做 $n$ 次樹形 DP $O(n^2)$ 地來求。
下面將以 $p_{rt,i}$ 表示以 $rt$ 為根時，$i$ 是否為必勝點 (只有一棵樹，即 $D=0$)。
還是考慮樹形 DP，設(shè) $g_i$ 表示在 $D=1$ 時，以 $1$ 為根，將第二棵樹的一個點 $y$ 拉過來當做 $i$ 子樹內(nèi)一個點的兒子，使 $i$ 成為必勝點（$i$ 可以原來就是必勝點）的方案數(shù)。
首先如果 $y$ 是一個必勝點，即 $p_{y,y}=true$，那么把它接過來沒有任何影響，所以我們在 $dp$ 狀態(tài)中認為 $y$ 是一個必敗點。(這里 $y$ 假設(shè)給定，即計算方案數(shù)時不需要考慮 $y$ 到底是第二棵樹的哪個點)。
下面除了 $y$ 節(jié)點，節(jié)點均指在原樹中的 (即第一棵樹)。

如果 $i$ 原來有 $\ge 2$ 個子節(jié)點 $j$ 是必敗點：
那么把 $y$ 接過來不會有任何影響，因為 $y$ 至多改變一個兒子的狀態(tài)，$g_i=size_i$。
如果 $i$ 原來有 $1$ 個兒子 $j$ 是必敗點：
(1) 那么我要么不把 $y$ 接在 $j$ 的子樹里，讓他還是必敗點，方案數(shù) $=size_i-size_j$。
(2) 要么把 $y$ 接在 $j$ 的子樹里，但是要使 $j$ 還是必敗點，方案數(shù) $=size_j-g_j$。
綜上 $g_i=size_i-g_j$。
如果 $i$ 原來一個兒子都不是必敗點：
那么我要使得讓他的一個兒子變成必敗點，$g_i=1 + \sum (size_j - g_j) = size_i - \sum g_j$（最開始 $+1$ 是因為可以直接接在 $i$ 下面）。

如果設(shè) $s_1$ 表示 $p_{y,y}=true$ 的 $y$ 的數(shù)量，$s_0$ 表示 $p_{y,y}=false$ 的 $y$ 的數(shù)量，那么有：
$ans = n\times s_1 \times p_{1,1} + g_1\times s_0$。
意思是，如果以 $1$ 為根時，$1$ 點是必勝點（即 $p_{1,1}=true$），那么第二棵樹里 $s_1$ 中的點可以隨便連，否則不能連。而 $s_0$ 中的點只能連在可以使 $1$ 點成為必勝點的那 $g_1$ 個點中。

再次提醒：$p_{rt,i},s_0,s_1$ 這些量都只是針對原樹而言，并沒有其他樹連進來；$g$ 只考慮的是 $D=1$ 的情況。
時間復(fù)雜度 $O(n^2)$。

在下面的討論中由于我們只用到了每一個 $p_{rt,rt}$，所以將以 $p_{rt}$ 代替 $p_{rt,rt}$。

當 $D>1$ 時：
直覺告訴我們肯定是從后往前 DP，設(shè) $f_{i,0}$ 表示遍歷到第 $i$ 棵樹，從第 $i$ 棵樹中選出一個必敗點連向第 $i-1$ 棵樹（具體連第 $i-1$ 棵樹的哪個點未定）的方案數(shù)。
$f_{i,1}$ 則是選出一個必勝點連向第 $i-1$ 棵樹。
由于我們每一次僅僅只需要挑出一個必勝點或必敗點，這意味著我們需要求出以每一個 $x$ 為根時，$g_x$ 的值，因此下面的討論將以 $g_x$ 表示以 $x$ 為根時，$g_x$ 的值，而不是以 $1$ 為根。
我們還是先暴力地做 $n$ 次樹形 DP 來得到這個東西。

如果第 $i+1$ 棵樹向第 $i$ 棵樹連進來的是必勝點，那么相當于沒有連，所以從第 $i$ 棵樹選出一個必敗點的方案為 $s_0$，選出一個必勝點的方案為 $s_1$，所以：
$f_{i+1,1}\times n\times s_0 \to f_{i,0}$
$f_{i+1,1}\times n\times s_1 \to f_{i,1}$
因為我們的 dp 狀態(tài)里規(guī)定了：具體連第 $i-1$ 棵樹的哪個點未定，所以第 $i+1$ 棵樹先隨便連一個點，再從那 $s_0/s_1$ 個點中選出一個點連向 $i-1$。
如果第 $i+1$ 棵樹向第 $i$ 棵樹連進來的是必敗點，那讓一個點 $x$ 成為必勝點的方案有 $g_x$ 種，成為必敗點的方案有 $n-g_x$ 種，所以：
$f_{i+1,0}\times \sum g_x \to f_{i,1}$
$f_{i+1,0}\times \sum (n-g_{x}) \to f_{i,0}$

綜上，得到轉(zhuǎn)移方程：
$f_{i,0}=f_{i+1,1}\times n\times s_0 + f_{i+1,0}\times \sum(n-g_x)$
$f_{i,1}=f_{i+1,1}\times n\times s_1 + f_{i+1,0}\times \sum g_x$
容易預(yù)處理出，$sum_1=\sum g_x,sum_0=\sum (n-g_x) = n^2 - sum_1$，所以轉(zhuǎn)移是 $O(1)$ 的。
邊界：$f_{D,0}=s_0,f_{D,1}=s_1$。
答案：$ans = n \times f_{1,1}\times p_1 + f_{1,0}\times g_1$。
時間復(fù)雜度 $O(n^2+D)$。

設(shè)計完狀態(tài)就是一些關(guān)于優(yōu)化的套路了，我們來看要優(yōu)化什么：

求 $p_x$。
求 $g_x$。
求 $f_{i,0/1}$。

$1,2$ 直接換根 DP：
設(shè) $up_i$ 表示以 $fa_i$ 為根時，去掉 $i$ 這棵子樹，$p_{fa_i}$ 的值。
$h_i$ 表示以 $fa_i$ 為根時，去掉 $i$ 這棵子樹，$g_{fa_i}$ 的值。
那么就可以用 $i$ 號節(jié)點兒子的 $p$ 和 $up_i$ 更新 $p_i$，兒子的 $g_i$ 和 $h_i$ 更新 $g_i$，更新方法類似。
那怎么求 $up$ 和 $h$ 呢？
會發(fā)現(xiàn) $up_i$ 只需要用 $up_{fa_i}$ 和 $p_u$ ( $u$ 是除了 $i$ 以外 $fa_i$ 的兒子) 類似更新。
$h_i$ 只需要用 $h_{fa_i}$ 和 $g_u$ ( $u$ 是除了 $i$ 以外 $fa_i$ 的兒子) 類似更新即可。

再來看 $3$ 的轉(zhuǎn)移：
$f_{i,0}=f_{i+1,1}\times n\times s_0 + f_{i+1,0}\times sum_0$。
$f_{i,1}=f_{i+1,1}\times n\times s_1 + f_{i+1,0}\times sum_1$。
這就非常的矩陣快速冪，因為只跟上一層的狀態(tài)和 $n,s_0,sum_0,s_1,sum_1$ 有關(guān)。
轉(zhuǎn)移矩陣就不寫了，手推即可。

DP 好題！點贊。

時間復(fù)雜度：$O(n + \log D)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,D;
int tot,head[N],to[N<<1],Next[N<<1]; 
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}

int Size[N],fa[N],p[N],g[N]; 
vector<int> son[N];
vector<int> V[N];   //V[u] 保存滿足 v 是 u 的兒子，且 p[v]=0 的 v
int Sumg[N];  //保存兒子的 g 的和 
void dfs1(int u,int Fa){
	fa[u]=Fa;
	Size[u]=1;
	p[u]=0;
	int cnt=0,failson=0,sumg=0;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		son[u].push_back(v);
		dfs1(v,u);
		Size[u]+=Size[v];
		if(p[v]==0) p[u]=1,cnt++,failson=v,V[u].push_back(v);
		(sumg+=g[v])%=mod;
	}
	Sumg[u]=sumg;
	if(cnt>=2) g[u]=Size[u];
	else if(cnt==1) g[u]=(Size[u]-g[failson]+mod)%mod;
	else g[u]=(Size[u]-sumg+mod)%mod;
}

int up[N],h[N];
void dfs2(int u){//在計算 up 和 h 時不能每一次都遍歷兄弟，不然碰到菊花就假了 
	if(fa[u]){
		up[u]=0;
		int cnt=0,failson_g=0,sumg=0;
		cnt=V[fa[u]].size();
		for(int v:V[fa[u]])   //這里遍歷兄弟至多只遍歷2個 
			if(v!=u){
				failson_g=g[v];
				break;
			} 
		sumg=(Sumg[fa[u]]-g[u]+mod)%mod;
		if(p[u]==0) cnt--;
		
		if(fa[fa[u]]){
			if(up[fa[u]]==0) cnt++,failson_g=h[fa[u]];
			(sumg+=h[fa[u]])%=mod;
		}
		
		if(cnt) up[u]=1;
		if(cnt>=2) h[u]=n-Size[u];  //注意此時整棵樹的大小要減去 Size[u] 
		else if(cnt==1) h[u]=(n-Size[u]-failson_g+mod+mod)%mod;
		else h[u]=(n-Size[u]-sumg+mod+mod)%mod;		
	}
	
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		dfs2(v);
	}
} 

int s0,s1,sum0,sum1;
void dfs3(int u){   //更新 p 和 g 
	p[u]=0;
	int cnt=0,failson_g=0,sumg=0;
	for(int v:son[u]){
		if(p[v]==0) p[u]=1,cnt++,failson_g=g[v];
		(sumg+=g[v])%=mod;
	}
	if(fa[u]){
		if(up[u]==0) p[u]=1,cnt++,failson_g=h[u];
		(sumg+=h[u])%=mod;
	}
	if(cnt>=2) g[u]=n;
	else if(cnt==1) g[u]=(n-failson_g+mod)%mod;
	else g[u]=(n-sumg+mod)%mod;
	
	if(p[u]==0) s0++;
	else s1++;
	(sum1+=g[u])%=mod,(sum0+=(n-g[u]+mod)%mod)%=mod;

	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		dfs3(v);
	}
}

struct Matrix{
	int a[2][2];
	int n,m;
	void Init(){
		memset(a,0,sizeof a);
	}
}F,A;
Matrix operator * (const Matrix &A,const Matrix &B){
	Matrix C;
	C.Init();
	C.n=A.n,C.m=B.m;
	for(int k=0;k<=A.m;k++){
		for(int i=0;i<=C.n;i++){
			for(int j=0;j<=C.m;j++){
				(C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod)%=mod;
			}
		}
	}
	return C;
}
Matrix Quick_power(Matrix A,int b){
	Matrix Ans;
	Ans.n=1,Ans.m=1;
	for(int i=0;i<=Ans.n;i++){    //單位矩陣 
		for(int j=0;j<=Ans.m;j++){
			if(i==j) Ans.a[i][j]=1;
			else Ans.a[i][j]=0;
		}
	}
	while(b){
		if(b&1) Ans=Ans*A;
		b>>=1,A=A*A;
	} 
	return Ans;
}
signed main(){
//	freopen("ball.in","r",stdin);
//	freopen("ball.out","w",stdout);
	n=read(),D=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
    
    dfs1(1,0);
    dfs2(1);
    dfs3(1);
    
    F.n=0,F.m=1;
    F.a[0][0]=s0,F.a[0][1]=s1;
    A.n=1,A.m=1;
    A.a[0][0]=sum0;
    A.a[0][1]=sum1;
    A.a[1][0]=s0*n%mod;
    A.a[1][1]=s1*n%mod;
    F=F*Quick_power(A,D-1);
    
	printf("%lld\n", (F.a[0][1]*n%mod*p[1]+F.a[0][0]*g[1]%mod)%mod );
	return 0;
}

62.[NOI Online #1 入門組] 跑步

首先題目等價于正整數(shù)拆分。
$f_{i,j}$：用前 $i$ 個數(shù)構(gòu)造的的不下降序列，和為 $j$ 的方案數(shù)。
那么 $f_{i,j}=f_{i-1,j}+f_{i,j-i}$，這就是完全背包
答案為。
$f_{n,n} $。

考慮根號分治，令 $B=\sqrt n$：

對于 $i<B$ 的部分我們?nèi)匀挥蒙厦娴?dp
設(shè) $g_{i,j}$ 表示構(gòu)造長度為 $i$ 的不上升序列，每個數(shù)都 $\ge B$，和為 $j$ 的方案數(shù)。
那么 $g_{i,j}=g_{i-1,j-B}+g_{i,j-i}$。意思是每一次我要么在序列末尾加一個 $B$，要么整體 $+1$。
由于 $j\le n$，所以 $i\le \sqrt n$。

最后答案就枚舉第一部分的和，$ans=\sum_{j=0}^n (f_{B-1,j}\times \sum_{k=0}^{\frac{n}{B}}g_{k,n-j})$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,mod,f[N],g[320][N];
signed main(){
	n=read(),mod=read();
	m=sqrt(n);
	f[0]=1;
	for(int i=1;i<m;i++){
		for(int j=i;j<=n;j++){
			(f[j]+=f[j-i])%=mod;
		}
	}
	g[0][0]=1;
	for(int i=1;i<=n/m+1;i++){
		for(int j=m*i;j<=n;j++){
			g[i][j]=(long long)(g[i][j-i]+g[i-1][j-m])%mod;
		}
	}
	
	long long ans=0;
	for(int j=0;j<=n;j++){
		long long sum=0;
		for(int k=0;k<=n/m;k++) (sum+=(long long)g[k][n-j])%=mod;
		(ans+=(long long)(f[j]*sum)%mod)%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

63.CF1220E Tourism

這題流行隨機化解法，又因為我以前沒寫過隨機化算法，所以就作為第一道隨機化題吧。

沒有奇環(huán)，讓我們想到黑白染色，所以我們隨機給每個點隨一個顏色。
每一次走的時候不能走相同顏色的邊，求解時可以簡單dp:
$f_{i,j}$ 表示當前走了 $i$ 條邊，走到 $j$ 的最短距離。
轉(zhuǎn)移 $O(k\times n^2)$ 顯然。

根據(jù)時間限制，我們可以隨機 $4500$ 次。

這個做法錯的可能只有一種，就是正確答案對應(yīng)的路徑上出現(xiàn)了顏色相同的相鄰點，否則一定可以 dp 出正確的答案。

所以這 $k$ 個點一共有 $2^k$ 總?cè)旧闆r，有且僅有 0101010... 或 1010101... 是對的，即一次正確的概率是：$\frac{1}{(2^{k-1})}=\frac{1}{512}$，錯誤的概率是：$\frac{511}{512}$。
$4500$ 次都不對的概率是 $(\frac{511}{512})^{4500} \approx 0.00015$，事實上可以隨到 $5000$ 次，那概率更低。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k,a[85][85];
int col[85],f[15][85],ans=LLONG_MAX;
void work(){
	for(int i=1;i<=n;i++) col[i]=rand()%2;
	for(int i=0;i<=k;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=0x3f3f3f3f3f3f3f3f;
		}
	}
	f[0][1]=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			for(int u=1;u<=n;u++){
				if(col[u]!=col[j])
					f[i][j]=min(f[i][j],f[i-1][u]+a[u][j]);
			}
		}
	}
	ans=min(ans,f[k][1]);
}
signed main(){
	srand(time(0));
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=read();
		}
	}
	int T=4500;
	while(T--) work();
	printf("%lld\n",ans);
	return 0;
}

64.采集

題目描述

有一棵 $n$ 個點（$n \le 10^4$）的樹，每個點有一個 $[1,n]$ 的顏色，請找出點數(shù)最少的連通塊，滿足這個連通塊有至少 $k$ 種不同的顏色（$k\le 5$）。

題解

因為 $k$ 很小，考慮隨機化亂搞。

首先給每個顏色隨機映射到 $[1,k]$。
如果最終的那 $k$ 種顏色剛好被映射成了不同的 $k$ 個
那么就正確，正確的概率是 $\frac{k!}{k^k}$ ，隨機 $50$ 次即可。

隨機完之后，考慮樹形 dp 計算答案，設(shè):
$f_{i,s}$ 表示 $i$ 這棵子樹內(nèi)選出集合 $s$ 的顏色的最小連通塊大小(一定要選 $i$)。
轉(zhuǎn)移每一次加進來一個子樹更新即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k;
int a[N];
int tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
}

int ans=INT_MAX,col[N];
int f[N][40];
void dfs(int u,int fa){
	f[u][1<<col[ a[u] ]]=1;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		for(int j=(1<<k)-1;j>=0;j--){
			for(int s=0;s<(1<<k);s++){
				f[u][j|s]=min(f[u][j|s],f[u][j]+f[v][s]);
			}
		}
	}
	ans=min(ans,f[u][(1<<k)-1]);
}
void work(){
	memset(f,0x3f,sizeof f);
	dfs(1,0);
}
signed main(){
	freopen("insect.in","r",stdin);
	freopen("insect.out","w",stdout);
	n=read(),k=read();
	bool flag=true;
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]>k) flag=false;
	} 
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	
	if(flag){
		for(int i=1;i<=k;i++) col[i]=i-1;
		work();
		printf("%d\n",ans);
		return 0;	
	}
	
	mt19937 mtrand(time(0));
	int T=50;
	while(T--){
		for(int i=1;i<=n;i++){
			col[i]=(unsigned int)mtrand()%k;
		}
		work();
	}
	printf("%d\n",ans);
	return 0;
}

65.[ABC214G] Three Permutations

來自題解區(qū)的妙妙非傳統(tǒng) DP 做法。

首先容斥是顯然的，設(shè) $dp_i$ 表示有 $i$ 個位置不符合條件的數(shù)量，那么：
$ans = \sum_{i=0}^n (-1)^i \times dp[i] \times (n-i)!$。

考慮進行一個經(jīng)典轉(zhuǎn)化：
將 $a_i$ 與 $b_i$ 連邊，那相當于我們要選出 $i$ 條邊，并給每條邊定向，并且不能有兩條邊指向同一個點。
如果這 $i$ 條邊給定了，那就是一個有 $n$ 個點， $i$ 條邊，每個點度數(shù)至多為 $2$ 的圖。
那一定是若干環(huán)加上若干鏈:

對于一個環(huán)，只有 $2$ 中定向方案；
對于一條鏈，最終一定是選出一個點，它左邊的邊全朝左，右邊的邊全朝右。所以一共有 $len$ 種方案，其中 $len$ 為鏈的大小。

但是我們不能暴力枚舉這 $i$ 條邊，所以考慮看到原圖，即：$n$ 個點，$n$ 條邊，每個點度數(shù)為 $2$ 的圖。這肯定是若干個環(huán)(有自環(huán))組成的圖。
設(shè) $f_{i,j}$ 表示前 $i$ 個環(huán)，選出 $j$ 條邊定向的總方案數(shù)。
設(shè)第 $i$ 個環(huán)的大小為 $sz$。
(目前為止都是主流做法，接下來就要開始神奇妙妙思路了)。

如果 $sz=1$，即是自環(huán)，那么要么選，要么不選：$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}$。
如果 $s\ne 1$，即正常的環(huán)，枚舉這個環(huán)選了 $k$ 條邊，則：$f_{i,j}=\sum_{k=0}^j f_{i-1,j-k}\times g_{sz,k}$。其中 $g_{sz,k}$ 表示在大小為 $sz$ 的環(huán)中，選 $k$ 條邊定向的方案數(shù)。

這個做法妙的地方就是求 $g$ 時不用 $dp$ 用組合意義：可以把一條 $(u,v)$ 的邊拆成 $(u,w)$ 和 $(w,v)$ ，定向朝 $u$ 就是選 $(u,w)$ 這條邊，否則選 $(w,v)$ 這條邊。
那么問題變成，給你 $2\times sz$ 個點的環(huán)，選出 $k$ 條不相鄰的邊的方案。
隨便考慮其中一條邊 $(a,b)$：

如果不選他，問題就變成在 $2\times sz$ 個點，$2\times sz - 1$ 條邊的鏈中選出 $k$ 條不相鄰邊的方案。可以認為是先給你 $2\times sz-k$ 個點，從中選出 $k$ 個點作為右端點，再在這些點左邊加上一個左端點。這樣剛好一共 $2\times sz$ 個點，且沒有選出的邊相鄰，并且這樣的結(jié)果也是可以唯一對應(yīng)到原鏈的即方案為 $C_{2\times sz-k}^k$。
如果選他，那它旁邊的邊不能選了，問題就變成在 $2\times sz-2$ 個點，$2\times sz-3$ 條邊的鏈中選出 $k-1$ 條不相鄰邊的方案，方案為 $C_{2\times sz-2-(k-1)}^{k-1}$。

所以對于不是自環(huán)的 $f$ 的轉(zhuǎn)移為：$f_{i,j} = f_{i-1,j} + \sum_{k=1}^j f_{i-1,j-k} \times ( C_{2\times sz-k}^k + C_{2\times sz-2-(k-1)}^{k-1})$。

這個復(fù)雜度看似是 $O(n^3)$ 但是其實是：
$O(\sum_{i=1}^{cnt} s_i\times sz_i)$。
其中 $s$ 是 $sz$ 的前綴和，$cnt$ 是環(huán)的總數(shù)。
而：

\[\begin{aligned} \sum_{i=1}^{cnt} s_i\times sz_i &= \sum_{i=1}^{cnt}(sz_1+sz_2+...+sz_i)\times sz_i \\ &= sz_1^2+sz_2^2+...+sz_{cnt}^2 + \sum_{1\le i<j\le cnt} sz_i\times sz_j \\ &< (sz_1+sz_2+...+sz_{cnt})^2 (展開即可) \\ &= n^2 \end{aligned} \]

所以時間復(fù)雜度是 $O(n^2)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3e3+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N],b[N];
int tot,head[N],to[N<<1],Next[N<<1];
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
} 

int fact[N<<1],inv[N<<1],q[N<<1];
void Init(){
	fact[0]=1;
	for(int i=1;i<N*2;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N*2;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	q[0]=1;
	for(int i=1;i<N*2;i++) q[i]=q[i-1]*inv[i]%mod;
}
int C(int n,int m){
	return fact[n]*q[m]%mod*q[n-m]%mod;
}

int cnt,sz[N],s[N];
bool vis[N];
void dfs(int u,int len){
	sz[cnt]=max(sz[cnt],len);
	vis[u]=true;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(vis[v]) continue;
		dfs(v,len+1);
	}
}

int f[N][N];

signed main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read(),add(a[i],b[i]),add(b[i],a[i]);
	
	Init();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			++cnt;
			dfs(i,1);
			s[cnt]=s[cnt-1]+sz[cnt];
		}
	}
	
	for(int i=0;i<=cnt;i++) f[i][0]=1;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=s[i];j++){
			f[i][j]=f[i-1][j];  //下面就不要算不選的情況了 
			if(sz[i]==1) (f[i][j]+=f[i-1][j-1])%=mod;
			else{
				for(int k=1;k<=min(j,sz[i]);k++){
					(f[i][j]+=f[i-1][j-k] * ( C(2*sz[i]-k,k) + C(2*sz[i]-1-k,k-1) )%mod)%=mod;
				} 
			}
		}
	} 
	
	int ans=0;
	for(int i=0;i<=n;i++){
		if(i&1) (ans=ans-f[cnt][i]*fact[n-i]%mod+mod)%=mod;
		else (ans+=f[cnt][i]*fact[n-i]%mod)%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

66.[NOI Online #2 提高組] 游戲

二項式反演板子。

因為恰好 $k$ 個不是很好算，所以考慮計算欽定 $k$ 個的情況。

考慮樹形 DP，設(shè) $f_{i,j}$ 表示 $i$ 子樹內(nèi)，選出 $j$ 對點，他們是非平局情況的方案數(shù)。
轉(zhuǎn)移就是經(jīng)典的樹形背包，先轉(zhuǎn)移不考慮根節(jié)點的情況，每一次合并進來一個子樹：$f_{u,x}\times f_{son,y} \to f_{u,x+y}$。
再考慮選根節(jié)點的情況，$f_{u,x}\times \max(cnt_{1-a_u}-x,0) \to f_{u,x+1}$ 其中 $cnt_{0/1}$ 表示 $u$ 子樹內(nèi) $0/1$ 類型的點的個數(shù)。

所以欽定 $k$ 對點的方案數(shù)為 $f_{1,k}\times (m-k)!$，如果設(shè)他是 $g_k$，那么有：
$g_k = \sum_{i=k}^m C_i^k \times ans_i$。
二項式反演可得：
$ans_k = \sum_{i=k}^m (-1)^{i-k} C_i^k \times g_i$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e3+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,a[N];
vector<int> G[N]; 
int f[N][N],g[N],tmp[N],Size[N],cnt[N][2];
void dfs(int u,int fa){
	cnt[u][a[u]]++;
	f[u][0]=1;
	for(int v:G[u]){
		if(v==fa) continue;
		dfs(v,u);
		cnt[u][0]+=cnt[v][0];
		cnt[u][1]+=cnt[v][1];
		for(int i=0;i<=Size[u]+Size[v];i++) tmp[i]=0;
		for(int x=0;x<=Size[u];x++){
			for(int y=0;y<=Size[v];y++){
				(tmp[x+y]+=f[u][x]*f[v][y]%mod)%=mod;
			}
		}
		for(int i=0;i<=Size[u]+Size[v];i++) f[u][i]=tmp[i];
		Size[u]+=Size[v];
	}
	for(int i=Size[u];i>=0;i--) (f[u][i+1]+=f[u][i]*max(0ll,cnt[u][1-a[u]]-i)%mod)%=mod;
	Size[u]++;
}

int fact[N],inv[N],q[N];
int C(int n,int m){
	return fact[n]*q[m]%mod*q[n-m]%mod;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(); m=n/2;
	string s; cin>>s;
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	q[0]=1;
	for(int i=1;i<N;i++) q[i]=q[i-1]*inv[i]%mod;
	
	for(int i=0;i<=m;i++) g[i]=f[1][i]*fact[m-i]%mod;	
	for(int i=0;i<=m;i++){
		int ans=0;
		for(int j=i;j<=m;j++){
			ans=(ans+( ((j-i)%2==0)?1:-1 )*C(j,i)%mod*g[j]%mod+mod)%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

67.CF1895F Fancy Arrays

題目的存在這個要求很不友好，考慮計算不合法情況，他的否命題是：$\forall i，ai<x 或 ai\ge x+k$。
因為有任意相鄰兩數(shù)的差不超過 $k$，所以上面這個條件等價于：每一個 $a_i$ 都 $<x$ 或者每一個 $a_i$ 都 $\ge x+k$。

還是不好算?
再一次看他的否命題，就得到了原命題的等價命題：$ \max(a_i)\ge x，\min(a_i)\le x+k-1$。當然還要滿足 $\forall i \in [2,n]，|a_i-a_{i-1}|\le k$，下面就統(tǒng)一省略后面這個條件了。
因為 $\max(a_i)<x$ 是 $\min(a_i)\le x+k-1$ 的充分條件，所以可以轉(zhuǎn)化為求:
$\min(a_i)\le x+k-1 的數(shù)列數(shù) - \max(a_i) < x 的數(shù)列數(shù)$。

先看前者：
如果知道了一個序列的差分數(shù)組就可以知道序列的每一個數(shù)與 $a_1$ 的差。
此時就可以知道哪個數(shù)是最小值，也就是說差分數(shù)組和最小值可以唯一確定一個序列。
差分數(shù)組的方案數(shù)是 $(2\times k+1)^{n-1}$，最小值的方案數(shù)是 $x+k$ （ $0$ 也算），所以總方案數(shù)就是 $(x+k) \times (2*k+1)^{n-1}$。

再看后者，因為 $x$ 很小，考慮 DP：
設(shè) $f_{i,j}$ 表示前 $i$ 個數(shù)，第 $i$ 個數(shù)是 $j$ 的方案數(shù)，那么：

\[f_{i,j}=\sum_{\max(0,j-k)\le y\le min(j+k,x-1)} f_{i-1,y} \]

矩陣快速冪優(yōu)化 DP 即可。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T;
int n,x,k;
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod,b>>=1;
	}
	return ans;
}
struct Matrix{
	int a[45][45];
	int n,m;
	void Init(){
		memset(a,0,sizeof a);
	}
}A,F;
Matrix operator * (const Matrix &A,const Matrix &B){
	Matrix C;
	C.Init();
	C.n=A.n,C.m=B.m;
	for(int k=0;k<A.m;k++){
		for(int i=0;i<C.n;i++){
			for(int j=0;j<C.m;j++){
				(C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod)%=mod;
			}
		}
	}
	return C;
}
Matrix Quick_power(Matrix A,int b){
	Matrix Ans;
	Ans.n=x,Ans.m=x;
	for(int i=0;i<Ans.n;i++){    //單位矩陣 
		for(int j=0;j<Ans.m;j++){
			if(i==j) Ans.a[i][j]=1;
			else Ans.a[i][j]=0;
		}
	}
	while(b){
		if(b&1) Ans=Ans*A;
		b>>=1,A=A*A;
	} 
	return Ans;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	T=read();
	while(T--){
		n=read(),x=read(),k=read();
		int ans=(x+k)*quick_power(2*k+1,n-1)%mod;
		
		A.Init(),F.Init();
		A.n=x,A.m=x;
		for(int i=0;i<x;i++){
			for(int j=0;j<x;j++){
				if(abs(j-i)<=k) A.a[i][j]=1;
			}
		}
		F.n=1,F.m=x;
		for(int i=0;i<x;i++) F.a[0][i]=1;
		A=Quick_power(A,n-1);
		F=F*A;
		for(int i=0;i<x;i++)
			ans=(ans-F.a[0][i]+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

68.[ARC162E] Strange Constraints

關(guān)于這種填數(shù)的題有一個經(jīng)典套路是按照值域從小到大或從大到小填數(shù)。
但是這里不好做，因為雖然第二個限制條件很好滿足，但是第三個限制條件由于我們不知道目前有哪些位置是可以填的所以不好轉(zhuǎn)移。

所以設(shè)計的狀態(tài)需要滿足對于第二個限制條件，前面的狀態(tài)要能限制到后面的狀態(tài)并且可以比較容易得出哪些位置可以填。
所以我們按照每個數(shù)在 $b$ 中出現(xiàn)的次數(shù)從大到小枚舉。
設(shè) $f_{i,j,k}$ 表示當前枚舉到的次數(shù)為 $i$，填完之后有 $j$ 個數(shù)已經(jīng)被填過了，有 $k$ 個位置已經(jīng)被填過了。
轉(zhuǎn)移時枚舉有 $x$ 個數(shù)被填了 $i$ 次，所以是從 $f_{i+1,j-x,k-i\times x}$ 轉(zhuǎn)移過來，轉(zhuǎn)移系數(shù)有下面這幾個，我們分別做解釋，設(shè) $cnt_{y}$ 表示 $A$ 中大于等于 $y$ 的數(shù)的個數(shù)：

$C_{cnt_i-(j-x)}^x$：
這是在從滿足條件二的數(shù)中選 $x$ 個數(shù)出來，因為 $i$ 是從大到小枚舉所以 $cnt_i$ 也包含了$ cnt_{i+1},cnt_{i+2},...$ 那些位置，即前面的 $j-x$ 個數(shù)也是從這 $cnt_i$ 個數(shù)里選出來的，不能再選了。
$C_{cnt_i-(k-i\times x)}^{i\times x}$：
這是在給這 $x$ 個數(shù)選位置，同理前面的 $k-i\times x$ 個位置也是從 $cnt[i]$ 個位置里選出來的，不能再選了。這也是這么設(shè)計狀態(tài)的原因，這就滿足了條件三。
$\frac{(i\times x)!} {(i!)^x}$：
這是可重集排列數(shù)。

這個 DP 貌似是 $O(n^4)$ 但是容易發(fā)現(xiàn) $j$ 和 $x$ 的枚舉范圍分別是 $\frac{n}{i}$ (因為 $i$ 從大到小枚舉) 和 $\frac{k}{i}$。
所以時間復(fù)雜度為：

\[\begin{aligned} O(\sum_{i：n \to 1}(\frac{n}{i} \times \sum_{1\le k \le n}\frac{k}{i})) &= O(n \times (∑\frac{1}{i} \times (\frac{1}{i} \times ∑k))) \\ &= O(\frac{n^2 (n+1)}{2} \times ∑\frac{1}{i^2} ) \end{aligned} \]

而 $∑\frac{1}{i^2}$ 可以省略，即時間復(fù)雜度是：$O(n^3)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=500+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[505],cnt[505],f[505][505][505];
int fact[N],inv[N],pre[N];
void Init(){
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	pre[0]=1;
	for(int i=1;i<N;i++) pre[i]=inv[i]*pre[i-1]%mod;
}
int C(int n,int m){
	if(m>n) return 0;
	return fact[n]*pre[m]%mod*pre[n-m]%mod;
}
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod,b>>=1; 
	}
	return ans;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
	for(int i=n;i>=1;i--) cnt[i]+=cnt[i+1];
	
	Init();
	
	f[n+1][0][0]=1;
	for(int i=n;i>=1;i--){
		for(int j=0;j<=n/i;j++){
			for(int k=0;k<=n;k++){
				for(int x=0;x<=min(j,k/i);x++){
					(f[i][j][k] += f[i+1][j-x][k-i*x]
								   * C(cnt[i]-(j-x) , x) % mod
								   * C(cnt[i]-(k-i*x) , i*x) % mod
								   * fact[i*x]%mod * quick_power(pre[i],x)%mod) %= mod;
				}
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<=n;i++) (ans+=f[1][i][n])%=mod;
	printf("%lld\n",ans);
	return 0;
}

69.[ARC163D] Sum of SCC

這題主要是要知道一個結(jié)論來把 SCC 這個一看就不好求得東西轉(zhuǎn)換一下。

結(jié)論：競賽圖的 SCC 的個數(shù)等于把這張圖的點集 $V$ 劃分成兩個集合(可以為空) $A$ 和 $B$ 且 $A$
與 $B$ 之間的邊方向都為 $A\to B$ 的劃分方案數(shù) $-1$。

證明:
考慮縮點，縮點之后的競賽圖也是一個形似鏈的競賽圖，他的拓撲序是唯一的。
如果拓撲序為 $p_1,p_2,...,p_k$（$k$ 為 SCC 的個數(shù)），那么對于任意的一個 $i(0\le i\le k)$ 我們以 $i$ 為斷點，$p_1,p_2,...,p_i$ 放進 $A$，$p_{i+1},...,p_k$ 放進 $B$ 就是一個合法的劃分方案。
又因為不能把一個 SCC 中的點分到兩個集合中（如果可以的話這必然不是個 SCC，因為劃分到 $B$ 中的點沒有到 $A$ 中的點的路徑），$B$ 中的 SCC 的拓撲序也不能比 $A$ 中的 SCC 的拓撲序小，所以這種劃分方案也是唯一的。
一共有 $k+1$ 種劃分方案。

接下來就是簡單 dp 了，設(shè) $f_{i,j,k}$ 表示已經(jīng)放了前 $i+j$ 個點，其中 $|A|=i$，$|B|=j$，并且一共有 $k$ 條邊滿足 $u<v$ 的方案數(shù)。
轉(zhuǎn)移時考慮新加進來編號為 $i+j+1$ 的點放到哪個集合：

放到 $A$ 集合，那么因為他是目前編號最大的點所以他連向 $B$ 中的那 $j$ 條邊均不符合條件,而他連向 $A$ 中的那 $i$ 條邊是隨便欽定的，枚舉其中有 $x$ 條邊滿足條件,轉(zhuǎn)移為：$f_{i,j,k}\times C_i^x \to f_{i+1,j,k+x}$。
放到 $B$ 集合，所以 $A$ 中連向他的那 $i$ 條邊均符合條件，而他連向 $B$ 中的那 $j$ 條邊是隨便欽定的，枚舉其中有 $x$ 條邊滿足條件,轉(zhuǎn)移為：$f_{i,j,k}\times C_j^x \to f_{i,j+1,k+i+x}$。

統(tǒng)計答案時，任意的一個方案都會給答案帶來 $1$ 的貢獻，不用去管哪些方案是一張圖的。
記得還要減去若干個 $1$。
時間復(fù)雜度 $O(n^3 \times m)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,f[35][35][905],ans;
int fact[N],inv[N],pre[N];
void Init(){
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	pre[0]=1;
	for(int i=1;i<N;i++) pre[i]=inv[i]*pre[i-1]%mod;
}
int C(int n,int m){
	return fact[n]*pre[m]%mod*pre[n-m]%mod;
}
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod,b>>=1; 
	}
	return ans;
}
signed main(){
	Init();
	n=read(),m=read();
	f[0][0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j+i<=n;j++){
			for(int k=0;k<=m;k++){
				for(int x=0;x<=i;x++)
					(f[i+1][j][k+x]+=f[i][j][k]*C(i,x)%mod)%=mod;
				for(int x=0;x<=j;x++)
					(f[i][j+1][k+i+x]+=f[i][j][k]*C(j,x)%mod)%=mod; 
			}
		}
	}
	for(int i=0;i<=n;i++){
		(ans+=f[i][n-i][m])%=mod;
	}
	(ans=ans-C(n*(n-1ll)/2ll,m)+mod)%=mod;
	printf("%lld\n",ans);
	return 0;
}

70.CF1728G Illumination

考慮容斥，枚舉集合 $S$ 表示 $S$ 中的這些點不被照亮，其他點隨意，則 $ans=\sum(-1)^{|S|} \times f_S$。
其中 $f_S$ 表示對應(yīng)的方案數(shù)。

首先每個不被照亮的點會對他周圍的燈的照亮范圍產(chǎn)生限制，并且兩個欽定點之間的路燈僅僅只受到這兩個點的限制。
這啟發(fā)我們預(yù)處理 $g_{l,r}$ 表示使得點 $p_l$ 和 $p_r$ 之間的路燈照不到 $p_l$ 和 $p_r$ 的方案數(shù)。
$O(nm^2)$ 預(yù)處理即可。

那么 $f_S= \prod g_{S_i,S_i+1}$。
注意到直接這么算是不對的，因為會漏了兩側(cè)的點，解決方法是加上 $-\infty$ 和 $+\infty$ 兩個點，并且欽定 $S$ 中一定要包含這兩個點（容易發(fā)現(xiàn)此時不影響 $|S|$ 的奇偶性）。

由此我們可以 $O(m2^m)$ 處理單個問題。

這里開始會出現(xiàn)兩種做法，一種是算出每個 $g_{l,r}$ 的容斥系數(shù)，動態(tài)加入一盞燈時算出他所影響的 $g$ 的貢獻。
但是比較麻煩且復(fù)雜度不優(yōu)，這里講第二種。

經(jīng)典套路之——容斥轉(zhuǎn) DP。
設(shè) $dp_i$ 表示只考慮前 $i$ 個點的答案，并且欽定第 $i$ 個點一定在容斥的集合 $S$ 里。
因為多加進來了一個點，所以原先容斥系數(shù)正的會變成負的，負的會變成正的，即轉(zhuǎn)移要帶上容斥系數(shù) $-1$。
$dp_i=\sum_{\substack{j<i}} (-1)\times dp_j\times g_{j,i}$。
初始狀態(tài)時 $dp[0]=-1$。
由這個轉(zhuǎn)移式子可以看出 $0$ 號點（無窮小) 是一定會被選的。
答案就是 $dp_{m+1}$ 因為 $m+1$ 號點也一定要被選。

單次 dp 復(fù)雜度 $O(m^2)$，每一次都做一遍就是 $O(Tn^2)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+5,mod=998244353,inf=INT_MAX;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int d,n,m,a[N],p[N],T;
int g[20][20],tmp[20][20],f[20];
signed main(){
	d=read(),n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++) p[i]=read();
	sort(p+1,p+m+1);
	p[0]=-inf,p[m+1]=inf;
	
	for(int l=0;l<=m+1;l++)
		for(int r=l+1;r<=m+1;r++)
			g[l][r]=1;
	for(int i=1;i<=n;i++)
		for(int l=0;l<=m+1;l++)
			for(int r=l+1;r<=m+1;r++)
				if(p[l]<=a[i]&&a[i]<=p[r])
					(g[l][r]*=min({d+1ll,a[i]-p[l],p[r]-a[i]}))%=mod; 
					
	for(int l=0;l<=m+1;l++)
		for(int r=l+1;r<=m+1;r++){
			tmp[l][r]=g[l][r];
		}
	
	T=read();
	while(T--){
		int x=read();
		for(int l=0;l<=m+1;l++)
			for(int r=l+1;r<=m+1;r++)
				if(p[l]<=x&&x<=p[r])
					(g[l][r]*=min({d+1,x-p[l],p[r]-x}))%=mod; 
		
		for(int i=0;i<=m+1;i++) f[i]=0;
		f[0]=-1;
		for(int i=1;i<=m+1;i++){
			for(int j=0;j<i;j++)
				(f[i]=f[i]-f[j]*g[j][i]%mod+mod)%=mod;
		}
		printf("%lld\n",f[m+1]);
		
		for(int l=0;l<=m+1;l++)
			for(int r=l+1;r<=m+1;r++)
				g[l][r]=tmp[l][r];		
	}
	return 0;
}

71.[ARC162D] Smallest Vertices

注意 $d_i$ 的定義是兒子的個數(shù)。

前置知識：Prufer序列，具體看 OI.wiki。
涉及結(jié)論：
對于給定每個點度數(shù)的所有本質(zhì)不同的 $n$ 個點的有標號無根樹一共有（ $deg_i$表示 $i$ 的度數(shù))：
$\frac{(n-2)!}{\prod(deg_i-1)!}$。

證明：
根據(jù) Prufer 序列的性質(zhì)，每個點在序列中出現(xiàn)的次數(shù)是 $deg_i-1$，所以我們可以根據(jù)度數(shù)還原出 Prufer 序列里面的元素種類，總共有 $(n-2)!$ 種順序，去掉重復(fù)的即為上述結(jié)果。

對于每一個點考慮計算他為好點的有根樹的數(shù)量，即拆分貢獻。
對于一個點 $u$ 如果他是好點意味著它子樹內(nèi)的點在 $[u,n]$ 范圍內(nèi)。
枚舉它的子樹大小 $sz$，且根據(jù) Prufer 序列他們的 $\sum (deg_i-1)=sz-2$。
注意到此時我們認為 $u$ 是根，所以他的 $deg_u=d_u$，其余點的 $deg_v=d_v+1$。
所以上面式子的要求即為 $\sum_{v∈subtree(u)} d_v = sz-1$。

容易想到背包，設(shè) $f_{i,j,k}$ 表示從 $[i,n]$ 中選出 $j$ 個點，他們的 $d$ 的和為 $k$ 的方案數(shù)。
轉(zhuǎn)移略。

那么對于 $u$ 子樹內(nèi)的貢獻就是：

\[ \frac{ (sz-2)! } { (d_u-1)! \times \prod _{v\ne u}d_v! } = \frac{ d_u \times (sz-2)! } { \prod d_v! } \]

對于 $u$ 子樹外的貢獻，此時我們把 $u$ 當做一個葉子結(jié)點，并且他子樹內(nèi)的那 $sz-1$ 個點刪掉再計算，
注意 $1$ 的度數(shù)也是 $d_1$,而不是 $d_1+1$，貢獻為：$\frac{ (n-sz+1-2)! \times d_1}{ \prod d_v! }$ ，其中 $v$ 不屬于 $u$ 的子樹（$u$ 此時為葉子的話他的度數(shù) $-1=0$，可以不考慮進去）。
把上面這兩個東西乘起來會發(fā)現(xiàn)分母剛好等于 $\prod_{i=1}^n d_i!$ ，可以直接預(yù)處理。

于是最后的貢獻就是：

\[f_{u+1,sz-1,sz-1-d_u} \times \frac{d_u \times d_1 \times (sz-2)! \times (n-sz+1-2)!}{\prod_{i=1}^n d_i!} \]

這里寫 $ f_{u+1,sz-1,sz-1-d_u}$ 而不是 $f_{u,sz,sz-1}$ 是因為不能出現(xiàn)不選 $u$ 的情況。

枚舉 $u$ 和 $sz$ 計算答案即可。

注意這里如果 $u$ 是根節(jié)點或者是葉子結(jié)點要特判一下 (因為 $sz\ge 2$，且 $u$ 子樹外不能為空) ，此時貢獻就是所有符合題意的無根樹的數(shù)量。

總時間復(fù)雜度 $O(n^3)-O(n^2)$（這個的意思是預(yù)處理 $O(n^3)$，求答案 $O(n^2)$）。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,d[N],f[505][505][505],ans;
int fact[N],inv[N],pre[N];
void Init(){
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	pre[0]=1;
	for(int i=1;i<N;i++) pre[i]=inv[i]*pre[i-1]%mod;
}
signed main(){
	Init(); 
	
	n=read();
	for(int i=1;i<=n;i++) d[i]=read();
	
	f[n+1][0][0]=1;
	for(int i=n;i>=1;i--){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n-1;k++){
				f[i][j][k]=f[i+1][j][k];
				if(j>0&&k>=d[i]) f[i][j][k]=(f[i][j][k]+f[i+1][j-1][k-d[i]])%mod;
			}
		}
	} 
	
	int tmp=1;
	for(int i=1;i<=n;i++) (tmp*=pre[d[i]])%=mod; //預(yù)處理分母
	 
	for(int u=1;u<=n;u++){
		if(u==1||d[u]==0)
			(ans += d[1] * fact[n-2] % mod * tmp % mod) %= mod;
		else
			for(int sz=2;sz<n;sz++){
				(ans += d[1] * fact[n-sz-1] % mod * d[u] % mod * fact[sz-2] % mod * f[u+1][sz-1][sz-1-d[u]] % mod * tmp % mod) %= mod;
			}
	}
	
	printf("%lld\n",ans);
	return 0;
}

72.[ABC306Ex] Balance Scale

根據(jù)題目意思可以連邊，如果沒有 = 相當于給每條邊定向。
因為不能出現(xiàn)環(huán)，所以相當于一個有標號 DAG 計數(shù)。

經(jīng)典思路設(shè) $f_S$ 表示 $S$ 中的點的導(dǎo)出子圖一共有多少種可能的 DAG。
因為一個 DAG 必然有一些入度為 $0$ 的點，考慮容斥這些點，去掉這些點仍然是個 DAG 那么：
$\sum_{T \in S} (-1)^{|T|} \times f_{S-T}$，$S-T$ 表示的是補集
這個東西算出來的結(jié)果表示的意義是 $S$ 中的點形成的 DAG 中有 $0$ 個入度為 $0$ 的點的方案數(shù)。
所以神奇的地方來了，因為這種 DAG 不存在，所以他等于 $0$。
那么移項即可得到：
$f_S=\sum_{T \in S，T\ne \emptyset}(-1)^{|T|+1} \times f_{S-T}$。
注意 $T$ 中的點之間不能有連邊。

加上 = 的情況也很簡單，其實相當于可以合并這條邊的兩個端點所以 $T$ 中的點就可以出現(xiàn)有連邊的情況，容斥系數(shù)從 $(-1)^{|T|+1}$ 變成 $(-1)^{cnt_T + 1}$ 即可，$cnt_T$ 為 $T$ 中的點的導(dǎo)出子圖的連通塊數(shù)量。
時間復(fù)雜度 $O(3^n)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m;
bool G[20][20];
int fa[20];
int get(int x){
	return (x==fa[x])?(x):(fa[x]=get(fa[x]));
}
void merge(int x,int y){
	fa[get(x)]=get(y);
}
int cnt[(1<<17)+5];  //預(yù)處理連通塊個數(shù) 
int f[(1<<17)+5];
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read();
		G[a][b]=G[b][a]=true;
	}
	
	for(int s=0;s<(1<<n);s++){
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(G[i][j]&&(s>>(i-1)&1)&&(s>>(j-1)&1))
					if(get(i)!=get(j)) merge(i,j);
			}
		}
		for(int i=1;i<=n;i++)
			if((s>>(i-1)&1)&&get(i)==i) cnt[s]++;
	}
	
	f[0]=1;
	for(int s=1;s<(1<<n);s++){
		for(int t=s;t;t=(t-1)&s){
			if((cnt[t]+1)&1) f[s]=(f[s]+mod-f[s^t])%mod;
			else f[s]=(f[s]+f[s^t])%mod;
		}	
	}
	
	printf("%lld\n",f[(1<<n)-1]);
	return 0;
}

73. [TJOI2018] 游園會

這應(yīng)該算是 dp 套 dp 板子。

下面稱輸入給出的獎?wù)麓疄?$s$，要求的兌獎串為 $t$。

會發(fā)現(xiàn)題目中的 $t$ 有三個限制：

長度為 $N$，且只有 N,O,I 三個字符。
與 $s$ 的 LIS 為 $len$。
不能出現(xiàn)子串 NOI。

會發(fā)現(xiàn)限制 $1$ 可以直接在 dp 轉(zhuǎn)移的時候滿足，限制 $3$ 直接多加一維狀態(tài) $0/1/2$ 表示現(xiàn)在的后綴和 NOI 的匹配位數(shù)即可。
即我們的 dp 狀態(tài)應(yīng)該是 $dp_{i,S,0/1/2}$ 表示填到 $t$ 的第 $i$ 位，當前狀態(tài)是 $S$，后綴和 NOI 的匹配位數(shù)是 $0/1/2$ 的方案數(shù)。
但是限制 $2$ 極其不好記錄狀態(tài)，因為你需要知道當前匹配到 $s$ 的第幾位，而直接記錄匹配到 $s$ 的第幾位的話又容易算重。

考慮我們是怎么判定一個給定的 $t$ 和 $s$ 的 LIS 是否為 $i$ 的。
顯然就是先求出他們的 LIS 再判斷。
這是一個經(jīng)典 dp，設(shè) $f_{i,j}$ 表示 $t[1,i]$ 和 $s[1,j]$ 匹配的 LIS，轉(zhuǎn)移：
$f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+(t_i==s_j))$。

發(fā)現(xiàn)我們要計算出 $f$ 第 $i$ 行的所有值，需要的只是 $t_i$ 和 $f$ 第 $i-1$ 行的所有值。
所以最外層 dp 的狀態(tài)的 $S$ 我們直接讓他表示內(nèi)層 dp 的第 $i$ 行的所有值。
外層 dp 的轉(zhuǎn)移就枚舉下一個位置 $t_{i+1}$ 是什么，并對第二維 $S$ 再做一遍 LIS 的那個 dp，得到新的狀態(tài) $S'$（即內(nèi)層 dp $f$ 數(shù)組的第 $i+1$ 行）。
這樣就轉(zhuǎn)移成功了。

但是很明顯 $S$ 的數(shù)量太多了，時間空間雙爆炸。
但顯然并不是所有的 $S$ 都是合法的。
因為 $0\le f_{i,j}-f_{i,j-1}\le 1$，所以 $S$ 表示的序列的差分數(shù)組每一位都一定是 $0/1$。
因此狀態(tài) $S$ 可以改為記錄內(nèi)層 dp $f$ 數(shù)組的第 $i$ 行的差分數(shù)組。
進一步地，可以直接狀壓成一個二進制數(shù)。
這樣 $S$ 的總數(shù)就是 $2^K$ 了。

狀態(tài)數(shù)是 $O(N2^K)$，轉(zhuǎn)移在 $O(1)$ 枚舉完 $t_{i+1}$ 之后需要對內(nèi)層 dp 進行 $O(K)$ 的轉(zhuǎn)移。
復(fù)雜度 $O(NK2^K)$。

轉(zhuǎn)移好函數(shù)的封裝并不難寫，實現(xiàn)參考了第一篇題解。
注意滾動數(shù)組并稍微剪枝。

因為在進行外層 dp 轉(zhuǎn)移的時候還要對內(nèi)層 dp 進行一次轉(zhuǎn)移，所以叫 dp 套 dp。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,mod=1e9+7;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int n,k,dp[2][(1<<15)+5][3],f1[20],f2[20],ans[20];
char s[20];
int Hash(int f[20]){   //把一個數(shù)組的差分數(shù)組狀壓
	int S=0;
	for(int i=0;i<k;i++) S+=(f[i+1]-f[i])*(1<<i);
	return S;
}
void decrypt(int f[20],int S){  //解壓縮
	for(int i=0;i<k;i++) f[i+1]=S>>i&1;
	for(int i=1;i<=k;i++) f[i]+=f[i-1];
}
void DP(int S,int newi,int newj,char c,int val){
	decrypt(f1,S);
	for(int i=1;i<=k;i++) f2[i]=max({f2[i-1],f1[i],f1[i-1]+(c==s[i])});
	int S2=Hash(f2);
	(dp[newi&1][S2][newj]+=val)%=mod;
}
signed main(){
	n=read(),k=read();
	scanf("%s",s+1);
	
	dp[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int S=0;S<(1<<k);S++) dp[i&1^1][S][0]=dp[i&1^1][S][1]=dp[i&1^1][S][2]=0;
		for(int S=0;S<(1<<k);S++){
			if(dp[i&1][S][0]){   //這個剪枝很重要
				DP(S,i+1,1,'N',dp[i&1][S][0]);
				DP(S,i+1,0,'O',dp[i&1][S][0]);
				DP(S,i+1,0,'I',dp[i&1][S][0]);
			}
			
			if(dp[i&1][S][1]){
				DP(S,i+1,1,'N',dp[i&1][S][1]);
				DP(S,i+1,2,'O',dp[i&1][S][1]);
				DP(S,i+1,0,'I',dp[i&1][S][1]);
			}
			
			if(dp[i&1][S][2]){
				DP(S,i+1,1,'N',dp[i&1][S][2]);
				DP(S,i+1,0,'O',dp[i&1][S][2]);
			}
		}
	}
	
	for(int S=0;S<(1<<k);S++){   //顯然 S 的 1 的個數(shù)就是這個內(nèi)層 dp DP 出來的 LIS 的長度
		(ans[__builtin_popcount(S)]+=((dp[n&1][S][0]+dp[n&1][S][1])%mod+dp[n&1][S][2])%mod)%=mod;
	}
	for(int i=0;i<=k;i++) printf("%d\n",ans[i]);
	return 0;
}

74.開心消消樂

題面

數(shù)據(jù)范圍： $N\le 1e5，T\le 10，N 是奇數(shù)$。

題解

考慮如何判斷一個沒有 ? 的序列合不合法。

題目中的操作不好順序處理，轉(zhuǎn)換一下：
相當于把原序列分成 $\lfloor \frac{n}{2} \rfloor$ 個塊 $[1,2],[3,4],[5,6],...,[n-2,n-1]$ 和最后一個數(shù)。
并維護一個棧，棧里面存儲的是塊。
我們一次考慮每個塊，如果當前考慮的塊是 $(x,y)$，那相當于有兩種操作：

把 $x$ 和棧中所有塊依次合并，直到棧中只剩一個數(shù) $z$，將 $(z,y)$ 放入棧。
直接把 $(x,y)$ 丟入棧。

考慮完所有塊后讓最后一個數(shù)和棧中的塊依次合并，最后得到的數(shù)就是結(jié)果。
判斷就是要判斷是否存在一種操作方式使得最后可以得到 $1$。
你會發(fā)現(xiàn)，我們其實不在乎這個棧具體長什么樣，只在乎當我們把一個數(shù) $x$ 和棧中的所有塊合并完之后會得到什么數(shù)。
即我們只需要維護棧所對應(yīng)的函數(shù) $f:x\to (a,b)$ 表示當 $x=0$ 時，會得到 $a$，當 $x=1$ 時會得到 $b$。
并且對于這兩種操作都可以快速更新出新的 $f$。

于是我們考慮 dp 設(shè) $dp_{i,a,b}$ 表示是否可以在考慮完第 $i$ 個塊之后得到函數(shù) $f:x\to (a,b)$。
轉(zhuǎn)移顯然，于是我們完成了判定。

對于計數(shù)，因為這個判定的 dp 的后兩維只有 $4$ 種情況，且 dp 值天然地只有 $0/1$ 兩種情況。
所以直接上 dp of dp 即可。
狀態(tài)數(shù)是 $O(2^4 \times n)$。

code

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second 
using namespace std;
const int N=1e5+5,mod=998244353;

inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int T,n;
char c[10],s[N];
int calc(char x,char y,char z){
	int u=x-'0',v=y-'0',w=z-'0';
	return c[(w<<2)+(v<<1)+u]-'0';
}
int dp[N][(1<<4)+5];
bool f1[2][2],f2[2][2];
int Hash(bool f[2][2]){
	return (f[0][0]<<3)+(f[0][1]<<2)+(f[1][0]<<1)+f[1][1];
}
void decrypt(bool f[2][2],int S){
	f[0][0]=S>>3&1;
	f[0][1]=S>>2&1;
	f[1][0]=S>>1&1;
	f[1][1]=S&1;
}
void DP(int newi,int S,char x,char y,int val){
	decrypt(f1,S);
	f2[0][0]=f2[0][1]=f2[1][0]=f2[1][1]=false;
	for(int a=0;a<=1;a++){
		for(int b=0;b<=1;b++){
			//轉(zhuǎn)移 1：先放 x，再放 y
			if(x=='0') f2[calc(a+'0',y,'0')][calc(a+'0',y,'1')]|=f1[a][b];
			else f2[calc(b+'0',y,'0')][calc(b+'0',y,'1')]|=f1[a][b];
			
			//轉(zhuǎn)移 2：把 (x,y) 直接丟進棧里
			int a1=calc(x,y,'0'),b1=calc(x,y,'1');
			if(a1==0&&b1==0) f2[a][a]|=f1[a][b];
			else if(a1==0&&b1==1) f2[a][b]|=f1[a][b];
			else if(a1==1&&b1==0) f2[b][a]|=f1[a][b];
			else f2[b][b]|=f1[a][b];
		}
	}
	int S2=Hash(f2);
	(dp[newi][S2]+=val)%=mod;
}
void work(){
	memset(dp,0,sizeof dp);
	dp[0][4]=1;
	for(int i=1;i<n;i+=2){
		int id=(i+1)/2;
		for(int S=0;S<(1<<4);S++){
			if(s[i]=='?'&&s[i+1]=='?'){
				DP(id,S,'0','0',dp[id-1][S]);			
				DP(id,S,'0','1',dp[id-1][S]);			
				DP(id,S,'1','0',dp[id-1][S]);			
				DP(id,S,'1','1',dp[id-1][S]);			
			}
			else if(s[i]=='?'){
				DP(id,S,'0',s[i+1],dp[id-1][S]);
				DP(id,S,'1',s[i+1],dp[id-1][S]);
			}
			else if(s[i+1]=='?'){
				DP(id,S,s[i],'0',dp[id-1][S]);
				DP(id,S,s[i],'1',dp[id-1][S]);
			}
			else DP(id,S,s[i],s[i+1],dp[id-1][S]);
		}
	}
	int id=(n-1)/2,ans=0;
	for(int S=0;S<(1<<4);S++){
		decrypt(f1,S);
		if(s[n]!='1') if(f1[1][0]||f1[1][1]) (ans+=dp[id][S])%=mod;
		if(s[n]!='0') if(f1[0][1]||f1[1][1]) (ans+=dp[id][S])%=mod;
	}
	printf("%d\n",ans);
}
signed main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",c,s+1);
		n=strlen(s+1);
		work();
	}
	return 0;
}

75. P1654 OSU!

根據(jù)初中數(shù)學：$(x+1)^3 = x^3 + 3\times x^2 + 3\times x + 1$。
所以每次增加一個一，答案的增加量為 $3\times x^2 + 3\times x + 1$。
所以我們只需要在每個位置維護增加量的期望即可。

我們分別維護 $f_i$ 表示以 $i$ 結(jié)尾的最長 $1$ 的個數(shù)的期望，即 $x$ 的期望；$g_i$ 表示以 $i$ 結(jié)尾的最長 $1$ 的個數(shù)的平方的期望，即 $x^2$ 的期望。
那么 $f$ 的轉(zhuǎn)移顯然: $f_i = p_i\times (f_{i-1}+1) + (1-p[i])\times 0 = p_i\times (f_{i-1}+1)$。
$g$ 的轉(zhuǎn)移由 $(x+1)^2=x^2+2x+1$ 可得: $g_i = p_i\times (g_{i-1}+2\times f_{i-1}+1) + (1-p_i)\times 0 = p_i\times (g_{i-1}+2\times f_{i-1}+1)$。
那么如果 $ans_i$ 表示前 $i$ 次操作的期望得分，就有：
$ans_i = ans_{i-1}+期望增加量 = ans_{i-1}+(3\times g_{i-1}+3\times f_{i-1}+1)\times p_i+(1-p_i)\times 0 = ans_{i-1}+(3\times g_{i-1}+3\times f_{i-1}+1)\times p_i$。
注意： 在這個式子里 $ans_{i-1}$ 并沒有放在 $p_i \times (...)$ 的括號里面，所以 $ans$ 表示的就是期望得分，而不是末尾 $x^3$ 的期望。

$n\le 100000$ 直接遞推即可，但顯然可以用矩陣快速冪進行加強。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n;
double p[N],f[N],g[N],ans[N];
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		scanf("%lf",&p[i]);
		f[i]=p[i]*(f[i-1]+1.0);
		g[i]=p[i]*(g[i-1]+f[i-1]*2.0+1.0);
		ans[i]=ans[i-1]+p[i]*(3.0*g[i-1]+3.0*f[i-1]+1.0);
	}
	printf("%.1lf\n",ans[n]);
	return 0;
}

76. Fluorescent

題意

一共有 $n$ 盞燈，$m$ 個開關(guān)，每個開關(guān)有對應(yīng)的操控燈的集合，按下開關(guān)可以使這些燈的轉(zhuǎn)臺翻轉(zhuǎn)。
求 $2^m$ 中開關(guān)狀態(tài)下，所有開著的燈的數(shù)量的立方的和。
數(shù)據(jù)范圍： $n\le 50，m\le 50$。

題解

主要考的是一個轉(zhuǎn)換，dp 倒不是很難。

設(shè) $x_i$ 表示第 $i$ 盞燈的狀態(tài)，$X$ 表示開著的燈的數(shù)量，那么：$X^3=(x_1+x_2+...+x_n)\times (x_1+x_2+...+x_n)\times (x_1+x_2+...+x_n) = \sum_{1\le i,j,k \le n} [x_i \land x_j \land x_k]$。
即滿足 $x_i=x_j=x_k=1$ 的有序三元組 $(i,j,k)$ 個數(shù)。

枚舉 $i,j,k$ 然后狀壓 dp 求解使他滿足 $x_i=x_j=x_k=1$ 的開關(guān)狀態(tài)的方案數(shù)。
設(shè) $f_{i,s}$ 表示前 $i$ 個開關(guān)，這三盞燈的狀態(tài)為 $s$ 的方案數(shù)，轉(zhuǎn)移顯然。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=50+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,m;
bool flag[N][N];
int f[N][10];
signed main(){
	T=read();
	for(int _=1;_<=T;_++){
		memset(flag,0,sizeof flag);
		n=read(),m=read();
		for(int i=1;i<=m;i++){
			int k=read();
			for(int j=1;j<=k;j++){
				int x=read();
				flag[i][x]=true;
			}
		}
		int ans=0;
		for(int x=1;x<=n;x++){
			for(int y=1;y<=n;y++){
				for(int z=1;z<=n;z++){
					memset(f,0,sizeof f);
					f[0][0]=1;
					for(int i=1;i<=m;i++){
						for(int s=0;s<(1<<3);s++){
							f[i][s]=f[i-1][s];
							int t=s;
							if(flag[i][x]) t^=1ll;
							if(flag[i][y]) t^=(1ll<<1);
							if(flag[i][z]) t^=(1ll<<2);
							(f[i][s]+=f[i-1][t])%=mod;
						}
					}
					(ans+=f[m][(1<<3)-1])%=mod;
				}
			}
		}
		printf("Case #%lld: %lld\n",_,ans);
	}
	return 0;
}

77. P3239 [HNOI2015] 亞瑟王

把每張牌的期望拆開計算，即設(shè): $P_i$ 表示第 $i$ 張牌被出的概率，那么，$E=\sum_{i=1}^n P_i\times d_i$。

直接計算 $P$ 并不好求，因為有每一輪只能出一張的限制，考慮計算一些輔助信息。
設(shè) $f_{i,j}$ 表示在 $r$ 輪中，前 $i$ 張牌總共出了 $j$ 張的概率。
那么對于 $P_i$,可以從 $f_{i-1,j}$ 轉(zhuǎn)移過來，轉(zhuǎn)移時，那 $j$ 輪因為在前 $i-1$ 張牌就被出掉了，所以不會考慮到 $i$，剩下的 $r-j$ 輪都會考慮到 $i$，那么這 $r-j$ 輪都不出的概率是 $(1-p_i)^{r-j}$，有一次出的概率是 $1-(1-p_i)^{r-j}$。
所以： $P_i=\sum_{j=0}^{i-1} f_{i-1,j} \times (1-(1-p_i)^{r-j})$。

接下來看 $f$ 的轉(zhuǎn)移。

$(1-p_i)^{r-j} \times f_{i-1,j} \to f_{i,j}$，表示 $i$ 這張牌一次都沒有出過，轉(zhuǎn)移系數(shù)的意義和上面一樣。
$( 1-(1-p_i)^{r-j+1} ) \times f_{i-1,j-1} \to f_{i,j}$，表示第 $i$ 張牌出過了，轉(zhuǎn)移系數(shù)意義同上。

復(fù)雜度：$O(Tn^2)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=220+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,r,d[N];
double p[N],P[N],f[N][N];
double quick_power(double a,int b){
	double ans=1.0;
	while(b){
		if(b&1) ans*=a;
		b>>=1,a*=a;
	}
	return ans;
}
signed main(){
	T=read();
	while(T--){
		n=read(),r=read();
		for(int i=1;i<=n;i++) cin>>p[i]>>d[i];
		memset(f,0,sizeof f);
		f[0][0]=1.0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=min(r,i);j++){
				f[i][j]=quick_power(1.0-p[i],r-j) * f[i-1][j] + ((j > 0) ? ((1.0 - quick_power(1.0-p[i],r-j+1)) * f[i-1][j-1]) : 0); 
			}
		}
		double ans=0;
		for(int i=1;i<=n;i++){
			P[i]=0;
			for(int j=0;j<=min(r,i-1);j++){
				P[i]+=f[i-1][j]*(1.0 - quick_power(1.0-p[i],r-j));
			}
			ans+=P[i]*d[i]*1.0;
		}
		printf("%.10lf\n",ans);
	}
	return 0;
}

78.P3600 隨機數(shù)生成器

首先根據(jù)期望的定義寫出：$E=\sum_{i=1}^x p_i \times i$。
其中 $p_i$ 表示最后的最大值為 $i$ 的概率。
但是這玩意非常不好算，所以變成前綴和形式，即：$p_i$ 表示最后的最大值 $\le i$ 的概率。
然后求得時候差分一下：$E=\sum_{i=1}^x (p_i-p_{i-1})\times i$。

怎么算 $p_i$?
最大值 $\le i$，意味著每一個區(qū)間的最小值都 $\le i$，也等價于每一個區(qū)間都有 $\le i$ 的數(shù)。
我們考慮一個經(jīng)典套路：當所有區(qū)間互不包含時，將區(qū)間左端點升序排序，則右端點也升序。
而在這道題里面，當一個區(qū)間包含另一個區(qū)間，那這個區(qū)間的 $min$ 一定 $\le$ 被包含的那個區(qū)間的 $min$，也就一點用也沒有了，可以刪掉。
設(shè) $g_j$ 表示選出 $j$ 個點，并使得每個區(qū)間都包含至少一個點的方案數(shù)，那么：$p_i = \frac {\sum g_j \times i^j \times (x-i)^{n-j}}{x^n}$。

下面假設(shè)已經(jīng)減去包含關(guān)系的區(qū)間，并將區(qū)間升序排序。

算 $g$ 就可以愉快的 dp 了。
設(shè) $f_{i,j}$ 表示在前 $i$ 個點中放 $j$ 個點，第 $i$ 個點必須放，使得覆蓋所有左端點小于等于 $i$ 的區(qū)間的方案數(shù)。
記 $l_i$ 表示最靠左的包含 $i$ 的區(qū)間，$r_i$ 表示最靠右的，容易知道那么 $l_i$ 到 $r_i$ 的區(qū)間都包含 $i$。
特殊的，如果沒有包含 $i$ 的區(qū)間那么 $r_i$ 表示最靠右的在 $i$ 左邊的區(qū)間，$l_i$ 此時等于 $r_i+1$。
轉(zhuǎn)移枚舉上一個放的點的位置： $f_{i,j}=\sum_{0\le k<i，r_k\ge l_i -1} f_{k,j-1}$。
前綴和優(yōu)化即可，$O(n^2)$。
那么 $g_j=\sum_{r_i=q} f_{i,j}$ ( $q$ 是去掉包含關(guān)系之后的區(qū)間數(shù)量)。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e3+5,mod=666623333;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,x,q;
struct P{
	int l,r;
}a[N]; 

int l[N],r[N],f[N][N],pre[N][N];  //pre[j][i]表示∑f[k][j](0<=k<=i) 
int g[N],p[N];
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod; 
		b>>=1,(a*=a)%=mod;
	}
	return ans;
}
signed main(){
	n=read(),x=read(),q=read();
	for(int i=1;i<=q;i++){
		a[i].l=read(),a[i].r=read();
	}
	
	for(int i=1;i<=q;i++){
		for(int j=1;j<=q;j++){
			if(a[j].l>n||i==j) continue;
			if(a[i].l<=a[j].l&&a[i].r>=a[j].r){
				a[i]={n+1,n+1};
				break;
			}
		}
	}
	sort(a+1,a+q+1,[](P x,P y){return x.l<y.l;});
	while(a[q].l>n) q--;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=q;j++){
			if(a[j].l<=i) r[i]=j;
			if(a[j].l<=i&&a[j].r>=i){
				if(!l[i]) l[i]=j;
			}
		}
		if(!l[i]) l[i]=r[i]+1;
	}
	
	f[0][0]=1;
	pre[0][0]=1; 
	for(int i=1;i<=n;i++) pre[0][i]=pre[0][i-1];
	for(int i=1;i<=n;i++){
		int k;
		for(int j=0;j<i;j++) 
			if(r[j]+1>=l[i]){
				k=j;
				break;
			}
		for(int j=1;j<=i;j++){
			if(k==0) f[i][j]=pre[j-1][i-1];
			else f[i][j]=(pre[j-1][i-1]-pre[j-1][k-1]+mod)%mod;
			pre[j][i]=(pre[j][i-1]+f[i][j])%mod;
		} 
	}
	
	for(int j=0;j<=n;j++){
		for(int i=0;i<=n;i++)
			if(r[i]==q) (g[j]+=f[i][j])%=mod; 
	}
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			( p[i] += g[j] * quick_power(i,j) % mod * quick_power(x-i,n-j) % mod * quick_power( quick_power(x,n) , mod-2 ) )%=mod; 
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		(ans+=(p[i]-p[i-1]+mod)%mod*i%mod)%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

79.CF1151F Sonya and Informatics

顯然的是最后一定是 000...1111，并且 0 的個數(shù)不變。
下面記 $m$ 為 0 的個數(shù)。

會發(fā)現(xiàn)這個 $k$ 很大，$n$ 很小，經(jīng)驗告訴我們最后的方法一定是用 dp 然后第一維表示操作次數(shù)，第二維大小為 $n$，然后矩陣加速。
在聯(lián)系第一句這個跟個廢話一樣的結(jié)論，可以設(shè)計出: $f_{i,j}$ 表示前 $i$ 次操作，使得前 $m$ 個數(shù)里有 $j$ 個 0 的方案數(shù)。
概率就是 $\frac {f_{k,m}}{(C^2_n)^k}$。
轉(zhuǎn)移還是比較顯然的：

把后面的 $m-j$ 個 0 和前面的 $m-j$ 個 1 中的一個換一下：$f_{i,j}\times (m-j)^2 \to f_{i+1,j+1}$。
把后面的 $n-m-m+j$ 個 1 和前面的 $j$ 個 0 中的一個換一下：$f_{i,j}\times (n-2\times m+j)\times j \to f_{i+1,j-1}$。
最后就是 $0$ 的個數(shù)不變的情況，容斥一下即可： $(\frac{n\times (n-1)}{2} - (m-j)^2 - (n-2\times m+j)\times j)\times f_{i,j} \to f_{i+1,j}$ 。

最后用矩陣加速即可。

code

int n,k;
int a[N],m;
struct Matrix{
	int n,m,a[105][105];
	void Init(){memset(a,0,sizeof a);}
}F,A;
Matrix operator * (const Matrix &A,const Matrix &B){
	Matrix C; C.Init();
	C.n=A.n,C.m=B.m;
	for(int k=0;k<=A.m;k++){
		for(int i=0;i<=C.n;i++){
			for(int j=0;j<=C.m;j++){
				(C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod)%=mod;
			}
		}
	}
	return C;
}
Matrix Quick_power(Matrix A,int b){
	Matrix Ans;
	Ans.n=n,Ans.m=n;
	for(int i=0;i<=Ans.n;i++){  
		for(int j=0;j<=Ans.m;j++){
			if(i==j) Ans.a[i][j]=1;
			else Ans.a[i][j]=0;
		}
	}
	while(b){
		if(b&1) Ans=Ans*A;
		b>>=1,A=A*A;
	} 
	return Ans;
}
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		b>>=1,a=a*a%mod;
	}
	return ans;
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read(),m+=(a[i]==0);
	int cnt=0;
	for(int i=1;i<=m;i++) cnt+=(a[i]==0);
	
	F.n=1,F.m=m; F.Init();
	F.a[1][cnt]=1;
	A.n=m,A.m=m;
	A.Init();
	for(int i=0;i<=m;i++){
		A.a[i][i+1]=(m-i)*(m-i);
		if(i>0) A.a[i][i-1]=(n-2*m+i)*i;
		A.a[i][i]=(n*(n-1)/2ll - (m-i)*(m-i) - (n-2*m+i)*i);
	}
	A=Quick_power(A,k);
	F=F*A;
	
	printf("%lld\n",F.a[1][m]*quick_power( quick_power(n*(n-1)/2ll,k) , mod-2)%mod); 
	return 0;
}

80. CF1737E Ela Goes Hiking

思維題，手玩可以發(fā)現(xiàn):
一開始那些往右的螞蟻一定會被他右邊第一只往左的螞蟻吃掉。
我們可以欽定第 $n$ 只螞蟻就是往左的，這是顯然正確的，如果他一開始是往右的他在碰到擋板之后就變成往左了。
于是所有往右的螞蟻一開始都會被吃掉，這可以看做第一個階段。

對于那些往左的若干個螞蟻他們在接下來的遭遇一定是:

第一只螞蟻掉頭和第二只螞蟻相遇，決出一個獲勝者，而不管是誰勝利，獲勝者都將與第三只螞蟻再次相遇
所以可以認為他們是合并了
由此不斷進行合并，直到剩余 $1$ 只螞蟻。

這是游戲的第二個階段。

在上述不斷合并的過程中我們關(guān)心的無非只有大小和編號，如果要讓第 $i$ 只螞蟻獲的最終勝利的話。
設(shè)一開始第 $i$ 只螞蟻前面的第一只向左的螞蟻是 $j$。
首先他得往左，那么它的初始重量是 $i-j$，因為他會吃掉 $(j,i)$ 中向右的螞蟻。
其次在前 $j$ 只螞蟻合并完之后，勝出的那個大螞蟻在和第 $i$ 只螞蟻決斗的時候第 $i$ 只螞蟻要勝出。
而大螞蟻無論編號是什么，他的重量一定是 $j$，所以 $i-j\ge j$，即 $j\le \lfloor \frac{i}{2} \rfloor$。
所以前 $\lfloor \frac{i}{2} \rfloor$ 只螞蟻隨便，$[\lfloor \frac{i}{2} \rfloor+1,i-1]$ 的螞蟻一定要向右，$i$ 一定要向左，方案數(shù)為 $2^{\lfloor \frac{i}{2} \rfloor}$。

接下來第 $i$ 只螞蟻變成 $i$，他要接著向右去決斗，接下來的問題相當于要給 $[i+1,n]$ 分段，設(shè)每一段的長度為 $len_1，len_2，...，len_m$。
那就要求:

$i>len_1$。
$i+len_1>len_2$。
$i+len_1+len_2>len_3$。
...

這種分段的一眼 dp, 設(shè) $f_i$ 表示第 $i$ 只螞蟻（重量為 $i$）吃掉 $[i+1,n]$ 的螞蟻，$[i+1,n]$ 螞蟻的分配方案數(shù)。
轉(zhuǎn)移枚舉后面第一個往左的螞蟻： $f_i=\sum_{i<j<2\times i} f_j$。

最后第 $i$ 只螞蟻的答案是 $\frac{2^{\lfloor \frac{i}{2} \rfloor} \times f_i}{2^{n-1}}$，$n-1$ 是因為一開始我們欽定了第 $n$ 只螞蟻是往左的。

復(fù)雜度是線性的。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,f[N],suf[N];
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		b>>=1,(a*=a)%=mod;
	}
	return ans;
}
signed main(){
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=2*n;i++) f[i]=suf[i]=0;
		f[n]=1;
		suf[n]=1;
		for(int i=n-1;i>=1;i--)	f[i]=(suf[i+1]-suf[2*i]+mod)%mod,suf[i]=(suf[i+1]+f[i])%mod;
		for(int i=1;i<=n;i++){
			printf("%lld\n",quick_power(2,i/2) * f[i] % mod * quick_power( quick_power(2,n-1) , mod-2) % mod);
		}
	}
	return 0;
}

81.[IOI 2008] Island

陳年老題，當時竟然沒過，所以這個份代碼其實是調(diào)出來的，代碼基本用以前寫的框架，碼風難評。

根據(jù)題意:
會給你一個基環(huán)樹森林，并且由渡船的規(guī)則可知，你離開一棵基環(huán)樹之后就不能回來了，所以等價于求每一棵基環(huán)樹的"直徑"(即最長簡單路徑)。

基環(huán)樹經(jīng)典思路就是以那個基環(huán)作為廣義的根節(jié)點，然后對每棵子樹分別求解，最后在環(huán)上合并。
基環(huán)樹的直徑有兩張可能:

在每棵子樹內(nèi)部
經(jīng)過基環(huán)上的若干條邊，起終點在兩棵不同的子樹內(nèi)。

所以我們先經(jīng)典樹形 DP，求出 $dp_i$ 表示 $i$ 子樹內(nèi)的直徑以及 $f_i$ 表示 $i$ 到他子樹內(nèi)的最長路徑。
那么第二種情況相當于求 $max(f_i+f_j+dist(i,j))$，$dist(i,j)$ 表示環(huán)上 $i,j$ 之間距離的最大值，有兩種可能。
斷環(huán)成鏈，復(fù)制兩遍。
對于斷環(huán)成鏈之后長度為 $2\times len$ 的鏈，兩點 $j<i$ 的答案為：$S_i-S_j+f_i+f_j$，$S$ 為前綴和數(shù)組。
即求在滿足 $i-len<j<i$ 的 $j$ 中 $f_j-S_j$ 的最大值，滑動窗口即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
inline int read(){
	int w = 1, s = 0;
	char c = getchar();
	for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
	for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
	return s * w;
}	
int n;
int head[N],to[N<<1],val[N<<1],Next[N<<1],deg[N],tot;
void add(int u,int v,int w){
	deg[v]++;
	to[++tot]=v,val[tot]=w,Next[tot]=head[u],head[u]=tot;
}

int id[N],num;   
void dfs(int u){
	id[u]=num;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(id[v]) continue;
		dfs(v);
	}
}
queue<int> q;    
bool flag[N];   //記錄拓撲排序時進過隊列的數(shù) 
void topo(){
	for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i); 
	while(q.size()){
		int u=q.front(); q.pop();
		flag[u]=1;	
		for(int i=head[u];i;i=Next[i]){
			int v=to[i];
			if(flag[v]) continue;
			deg[v]--;
			if(deg[v]==1) q.push(v);
		}
	}	
} 

int dp[N],f[N]; 
int F[N];  //記錄每棵基環(huán)樹里的最長鏈：有兩種情況
void dfs1(int u,int fa,int rt){	
	for(int i=head[u];i;i=Next[i]){
		int v=to[i],w=val[i];
		if(v==fa||!flag[v]) continue;
		dfs1(v,u,rt);
		dp[rt]=max(dp[rt],f[u]+f[v]+w);
		f[u]=max(f[u],f[v]+w); 
	}
}

bool stater[N];
int cnt,hoop[N<<1],pre[N<<1];
deque<int> dq;
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		int v=read(),w=read();
		add(i,v,w),add(v,i,w);
	}
	
	for(int i=1;i<=n;i++){  //找出每一棵基環(huán)樹，并給同一棵基環(huán)樹上的點編號
		if(!id[i]){
			++num;
			dfs(i);
		}
	}
	
	topo();//拓撲排序 
	
	for(int u=1;u<=n;u++){
		if(!stater[u]&&!flag[u]){
			cnt=0;
			hoop[++cnt]=u,pre[cnt]=0;
			int x=u,tmp;
			while(!stater[x]){
				stater[x]=true;
				for(int i=head[x];i;i=Next[i]){
					int y=to[i],w=val[i];
					if(!flag[y]&&!stater[y]){
						x=y,hoop[++cnt]=y,pre[cnt]=w;
						break;
					}
					else if(y==u) tmp=w;
				}
			}
			hoop[++cnt]=u,pre[cnt]=tmp;
			int len=cnt-1;  //環(huán)長，注意到 hoop[cnt] 此時是 u, 
			for(int i=2;i<=len;i++) hoop[++cnt]=hoop[i],pre[cnt]=pre[i];
			for(int i=2;i<=2*len;i++) pre[i]+=pre[i-1];
			for(int i=1;i<=len;i++)
				dfs1(hoop[i],0,hoop[i]),F[id[u]]=max(F[id[u]],dp[hoop[i]]);
			
			
			while(dq.size()) dq.pop_back();
			dq.push_front(1);
			for(int i=2;i<=2*len;i++){
				while(dq.size()&&dq.front()<=i-len) dq.pop_front();
				int j=dq.front();
				F[id[u]]=max(F[id[u]],f[hoop[i]]+pre[i]+f[hoop[j]]-pre[j]);
				while(dq.size()&&f[hoop[dq.back()]]-pre[dq.back()] <= f[hoop[i]]-pre[i]) dq.pop_back();
				dq.push_back(i);
			}
		}
	}	
	
	int ans=0;
	for(int i=1;i<=num;i++) ans+=F[i];
	printf("%lld\n",ans);
	return 0;
}

82.不條理狂詩曲

考慮分治，思考如何計算跨越 $mid$ 的區(qū)間的答案。

可以用 $dp$ 求出:
$fl_i$：表示區(qū)間 $[i,mid]$ , $a_{mid}$ 可選可不選，選擇若干不相鄰的數(shù)的和的最大值。
$gl_i$：表示區(qū)間 $[i,mid]$ , $a_{mid}$ 不選，選擇若干不相鄰的數(shù)的和的最大值。
$fr_i$：表示區(qū)間 $[mid+1,i]$ , $a_{mid+1}$ 可選可不選，選擇若干不相鄰的數(shù)的和的最大值。
$gr_i$：表示區(qū)間 $[mid+1,i]$ , $a_{mid+1}$ 不選，選擇若干不相鄰的數(shù)的和的最大值。
那么一個區(qū)間 $[i,j]，(i\le mid,j\ge mid+1)$ 的答案為 $max(fl_i+gr_j,gl_i+fr_j)$。
如果這個東西的值為第二項那么: $fl_i-gl_i<fr_j-gr_j$。

把左邊按照 $fl_i-gl_i$ 排序(不要取模)，并求一下排序后，$gl_i$ 的前綴和以及 $fl_i$ 的后綴和。
對于右邊的每一個 $j$，二分找到最后一個 $fl_i-gl_i<fr_j-gr_j$ 的 $i$，那么所有以 $j$ 為右端點的區(qū)間的答案為：$fr_j\times (i-l+1)+pre_i + gr_j\times (mid-i)+suf_{i+1}$。

復(fù)雜度為 $O(n\log ^2 n)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N],ans;
int fl[N],gl[N],fr[N],gr[N],pre[N],suf[N];
struct P{
	int x,y,c;
}b[N];
int find(int l,int r,int x){
	int res=l-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid].c<x) res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
void solve(int l,int r){
	if(l==r){
		(ans+=a[l])%=mod;
		return;
	}
	int mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	
	for(int i=l;i<=mid+1;i++) fl[i]=gl[i]=0;
	for(int i=mid;i<=r;i++) fr[i]=gr[i]=0;
	
	gl[mid]=0,fl[mid]=a[mid];
	for(int i=mid-1;i>=l;i--){
		fl[i]=max(fl[i+1],fl[i+2]+a[i]);
		gl[i]=max(gl[i+1],gl[i+2]+a[i]);
	}
	fr[mid+1]=a[mid+1],gr[mid+1]=0;
	for(int i=mid+2;i<=r;i++){
		fr[i]=max(fr[i-1],fr[i-2]+a[i]);
		gr[i]=max(gr[i-1],gr[i-2]+a[i]);
	}
	
	for(int i=l;i<=mid;i++) b[i]={fl[i],gl[i],fl[i]-gl[i]};
	sort(b+l,b+mid+1,[](P x,P y){return x.c<y.c;});
	pre[l-1]=0;
	for(int i=l;i<=mid;i++) pre[i]=(pre[i-1]+b[i].y)%mod;
	suf[mid+1]=0;
	for(int i=mid;i>=l;i--) suf[i]=(suf[i+1]+b[i].x)%mod;
	
	for(int j=mid+1;j<=r;j++){
		int i=find(l,mid,fr[j]-gr[j]);
		(ans+=fr[j]*(i-l+1)%mod+pre[i]+gr[j]*(mid-i)%mod+suf[i+1])%=mod;
	}
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	
	solve(1,n);
	
	printf("%lld\n",ans);
	return 0;
}

83.Sum

首先會發(fā)現(xiàn)一個性質(zhì)：
一組里面的數(shù)要么全選，要么全不選，最多只有一組數(shù)是只選了一部分的。

證明:
如果有兩組數(shù)，分別選了一部分，那么比較它們的隊尾 $x,y$ 如果 $x>y$ 那么完全可以把 $y$ 去掉，選 $x$ 的下一個，因為他保證了每一組非嚴格單增。

線段樹分治即可，遞歸到葉子的時候就把他當做那個沒選滿的組。

時間復(fù)雜度：$O(nk\log n)$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3e3+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k,t[N],f[N],ans;  //背包數(shù)組f[i]要求恰好放滿
vector<int> a[N];  
void solve(int l,int r){
	if(l==r){
		for(int i=0;i<=k;i++) ans=max(ans,f[i]+a[l][min(t[l],k-i)]);
		return; 
	}
	vector<int> tmp;
	for(int i=0;i<=k;i++) tmp.push_back(f[i]);
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++){
		for(int j=k;j>=t[i];j--) f[j]=max(f[j],f[j-t[i]]+a[i][t[i]]);
	}
	solve(mid+1,r);
	for(int i=0;i<=k;i++) f[i]=tmp[i];
	for(int i=mid+1;i<=r;i++){
		for(int j=k;j>=t[i];j--) f[j]=max(f[j],f[j-t[i]]+a[i][t[i]]);
	}
	solve(l,mid);
	for(int i=0;i<=k;i++) f[i]=tmp[i];
	tmp.clear();   //及時釋放 
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		t[i]=read();
		a[i].push_back(0);
		for(int j=1;j<=t[i];j++) a[i].push_back(read()),a[i][j]+=a[i][j-1];
	}
	memset(f,-0x3f,sizeof f); 
	f[0]=0;
	solve(1,n);
	printf("%lld\n",ans);
	return 0;
}

84. [PA 2021] Od deski do deski

設(shè) $f_i$ 表示是否可以刪完前 $i$ 個數(shù)，轉(zhuǎn)移很簡單，$a_j=a_i$，$f_{j-1}\to f_i$。
我們定義一個顏色 $c$ 是好顏色，當且僅當目前存在一個 $j$ 滿足：

$a_j=c$。
$f_{j-1}=true$。

所以如果有一個 $i$ 和某個好顏色顏色一樣，那么 $f_i$ 一定 $=true$。

于是設(shè) $g_{i,j,0/1}$ 表示前 $i$ 個數(shù)，有 $j$ 個好顏色，$f_i=0/1$ 的序列個數(shù)。
轉(zhuǎn)移時分類討論：

$f_i=0$ 且 $a_{i+1}$ 和某個好顏色一樣：$g_{i,j,0} \times j \to g_{i+1,j,1}$。
$f_i=0$ 且 $a_{i+1}$ 和之前任意一個好顏色都不一樣：$g_{i,j,0} \times (m-j) \to g_{i+1,j,0}$。
$f_i=1$ 且 $a_{i+1}$ 和某個好顏色一樣：$g_{i,j,1} \times j \to g_{i+1,j,1}$。
$f_i=1$ 且 $a_{i+1}$ 和之前任意一個好顏色都不一樣，注意這個時候 $a_{i+1}$ 成為了一個從沒出現(xiàn)過的好顏色：$g_{i,j,1} \times (m-j) \to g_{i+1,j+1,0}$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3e3+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,g[N][N][2];
signed main(){
	freopen("del.in","r",stdin);
	freopen("del.out","w",stdout);
	n=read(),m=read();
	g[0][0][1]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=min(i,m);j++){
			(g[i+1][j][1]+=g[i][j][0]*j%mod)%=mod;
			(g[i+1][j][0]+=g[i][j][0]*(m-j)%mod)%=mod;
			(g[i+1][j][1]+=g[i][j][1]*j%mod)%=mod; //相同的好顏色算一個
			(g[i+1][j+1][0]+=g[i][j][1]*(m-j)%mod)%=mod; 
		}
	}	
	int ans=0;
	for(int j=0;j<=min(n,m);j++) (ans+=g[n][j][1])%=mod;
	printf("%lld\n",ans);
	return 0;
}

85.Divan and Kostomuksha (hard version)

如果設(shè) $g_i=\gcd(a_1,a_2,...,a_i)$，那么 $g$ 是個單調(diào)遞減的數(shù)列。
考慮 dp，設(shè) $f_i$ 表示最后答案的每個 $g_j$ 都是 $i$ 的倍數(shù)的權(quán)值的最大值（當然不一定可以湊出 $n$ 個 $g_j$，具體可以看轉(zhuǎn)移方程來理解）。
為了求這個，我們先預(yù)處理：$c_i$ 表示 $a$ 序列中 $i$ 的倍數(shù)的個數(shù)。
那么 dp 時我們從大到小枚舉 $i$，因為每個 $g_j$ 都要是 $i$ 的倍數(shù)，所以我們只能從 $i$ 的倍數(shù) $k$ 轉(zhuǎn)移過來,方程為：$f_i=f_k+(c_i-c_k)\times i$。
意思是，在 $f_k$ 所對應(yīng)的 $a$ 序列后面，再加上 $c_i-c_k$ 個 $i$ 的倍數(shù)，但不是 $k$ 的倍數(shù)的數(shù)。
初始值：$f_i=i\times c_i$。
答案就是所有 $c_i=n$ 的 $f_i$ 的最大值，因為要滿足能構(gòu)成一個長度為 $n$ 的 $g$ 序列。

轉(zhuǎn)移時直接枚舉倍數(shù)雖然也是調(diào)和級數(shù)，但會被卡，所以可以只枚舉 $k=i\times p$（$p$ 是質(zhì)數(shù)）的 $k$，正確性也是顯然的，如果一個 $k'=i\times p \times x$，那么在 $k$ 的轉(zhuǎn)移時已經(jīng)轉(zhuǎn)移過 $k'$，這里就沒必要再轉(zhuǎn)移了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=20000000+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N],maxn,cnt[M],c[M];
long long f[M],ans;
int m,pri[6000000];
bool stater[M];
void Eular(){
	stater[1]=true;
	for(int i=2;i<M;i++){
		if(!stater[i]) pri[++m]=i;
		for(int j=1;j<=m&&(long long)(pri[j]*i)<(long long)M;j++){
			stater[i*pri[j]]=true;
			if(i%pri[j]==0) break;
		}
	}
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Eular();
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),maxn=max(maxn,a[i]),cnt[a[i]]++;
	for(int i=1;i<=maxn;i++)
		for(int j=i;j<=maxn;j+=i)
			c[i]+=cnt[j];
	for(int i=maxn;i>=1;i--){
		f[i]=1ll*i*c[i];
		for(int j=1;j<=m&&pri[j]*i<=maxn;j++){
			f[i]=max( f[i],f[i*pri[j]]+1ll*i*(c[i]-c[i*pri[j]]) );
		}
		if(c[i]==n){
			ans=max(ans,f[i]);
		} 
	}
	printf("%lld\n",ans);
	return 0;
}

86.小 Y 和恐怖的奴隸主

首先設(shè) $f_{i,a,b,c}$ 表示第 $i$ 次攻擊后有 $a$ 個 $1$ 血仆從，$b$ 個 $2$ 血仆從，$c$ 個 $3$ 血仆從的概率，$g_i$ 表示 $i$ 次攻擊的期望扣血量。
$g,f$ 的轉(zhuǎn)移是顯然的。

注意到要滿足 $a+b+c\le k$。
所以 $f$ 的合法的狀態(tài)數(shù)比較少,只有 $165$，然后加上 $g$ 的話一共 $166$ 個狀態(tài)。

所以考慮狀壓之后矩陣快速冪轉(zhuǎn)移，然后直接跑是 $O(T \times 166^3 \times \log n)$ 會 TLE。
但是可以預(yù)處理出所有 $2$ 的冪次的矩陣，這樣只需要用一個初始向量乘以 $\log n$ 個矩陣即可。
復(fù)雜度變?yōu)椋?span id="w0obha2h00" class="math inline">$O(166^3 \times \log n + T \times 166^2 \times \log n)$。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,m,k,inv[N];
int quick_power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod,b>>=1; 
	}
	return ans;
}
void work1(){
	while(T--){
		int n=read(),ans=quick_power(inv[2],n)*n%mod;
		for(int i=1;i<=n;i++)
			(ans += quick_power(inv[2],i)*(n-1)%mod )%=mod;
		printf("%lld\n",ans);
	}
} 

struct Matrix{
	int n,m,a[167][167];
	void Init(){
		memset(a,0,sizeof a);
	}
}F,A[100];
Matrix operator * (Matrix &A,Matrix &B){
	Matrix C; C.Init();
	C.n=A.n,C.m=B.m;
	for(int i=1;i<=C.n;i++){
		for(int j=1;j<=C.m;j++){
			__int128 tmp=0;
			for(int k=1;k<=A.m;k++){
				tmp+=A.a[i][k]*B.a[k][j];
			}
			C.a[i][j]=tmp%mod;
		}
	}
	return C;
}

int cnt,id[10][10][10];
void Init2(){
	for(int a=0;a<=k;a++){
		for(int b=0;a+b<=k;b++){
			id[a][b][0]=++cnt;
		}
	} 
	++cnt;  //表示記錄boss扣血期望 
	for(int a=0;a<=k;a++){
		for(int b=0;a+b<=k;b++){
			int ID=id[a][b][0],Inv=inv[a+b+1];  //Inv表示攻擊場上任何一個人的概率 
			if(a) A[0].a[ID][ id[a-1][b][0] ]=Inv*a%mod;
			if(b){
				if(a+b<k) A[0].a[ID][ id[a+1][b][0] ]=Inv*b%mod;
				else A[0].a[ID][ id[a+1][b-1][0] ]=Inv*b%mod;
			}
			A[0].a[ID][ID]=Inv;  //表示攻擊到boss
			A[0].a[ID][cnt]=Inv;  //轉(zhuǎn)移到表示期望的那個狀態(tài) 
		}
	} 	
	A[0].a[cnt][cnt]=1;  //注意每次操作要繼承上一次操作的期望
	A[0].n=A[0].m=cnt; 
}
void Init3(){
	for(int a=0;a<=k;a++){
		for(int b=0;a+b<=k;b++){
			for(int c=0;a+b+c<=k;c++){
				id[a][b][c]=++cnt;
			}
		}
	} 
	++cnt; 
	for(int a=0;a<=k;a++){
		for(int b=0;a+b<=k;b++){
			for(int c=0;a+b+c<=k;c++){
				int ID=id[a][b][c],Inv=inv[a+b+c+1];  
				if(a) A[0].a[ID][ id[a-1][b][c] ]=Inv*a%mod;
				if(b){
					if(a+b+c<k) A[0].a[ID][ id[a+1][b-1][c+1] ]=Inv*b%mod;
					else A[0].a[ID][ id[a+1][b-1][c] ]=Inv*b%mod;
				}
				if(c){
					if(a+b+c<k) A[0].a[ID][ id[a][b+1][c] ]=Inv*c%mod;
					else A[0].a[ID][ id[a][b+1][c-1] ]=Inv*c%mod; 
				}
				A[0].a[ID][ID]=Inv; 
				A[0].a[ID][cnt]=Inv; 
			} 
		}
	} 	
	A[0].a[cnt][cnt]=1; 
	A[0].n=A[0].m=cnt; 
}

signed main(){
//	freopen("patron.in","r",stdin);
//	freopen("patron.out","w",stdout);
	T=read(),m=read(),k=read();
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	
	if(m==1){
		work1();
		return 0;
	} 
	if(m==2) Init2();
	else Init3();
	for(int i=1;i<=60;i++) A[i]=A[i-1]*A[i-1];
	while(T--){
		int n=read();
		F.Init();
		F.n=1,F.m=cnt; 
		if(m==2) F.a[1][ id[0][1][0] ]=1;
		else F.a[1][ id[0][0][1] ]=1;
		for(int i=0;i<=60;i++)
			if(n>>i&1) F=F*A[i];
		printf("%lld\n",F.a[1][cnt]);
	}
	return 0;
}

87.阿兒克

題面

一個圓上有 $3n$ 個點，一共有 $n$ 種顏色，且每種顏色恰好 $3$ 個點，問有多少種把這個圓分成 $n$ 段圓弧的方式，使得：

任意兩段圓弧不交。
每一個圓弧的兩個端點顏色都為 $c$，且不經(jīng)過另一個顏色為 $c$ 的端點。

數(shù)據(jù)范圍： $n\le 2e5$。

題解

每個顏色很明顯只有三種連接方式，于是可以枚舉顏色 1 用的是哪種連接方法，這樣變成鏈上的問題了。

恰好 $n$ 段圓弧不太好刻畫，于是我們可以先求出 $f_i$ 表示前 $i$ 個數(shù)里最多可以連出多少圓弧，以及此時的方案數(shù)。
用一個 pair 記錄。
轉(zhuǎn)移是顯然的。

最后只要合并三種情況即可，如果最多的圓弧個數(shù)不足 $n-1$(因為第 $1$ 種顏色去掉了) 個答案就是 $0$。

code

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long 
using namespace std;
const int N=2e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N*6],t[N];
PII operator +(PII x,PII y){   //重載 + 運算符 
	if(y.fi==x.fi) (x.se+=y.se)%=mod;
	else if(y.fi>x.fi) x=y;
	return x;
}
PII f[N*6];
int pre[N*6],lst[N*6];
PII solve(int l,int r){  //表示對 [l,r] 進行 DP 
	for(int i=1;i<=n/3;i++) lst[i]=0;
	for(int i=l;i<=r;i++){
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	f[l-1]={0,1};
	for(int i=l;i<=r;i++){
		f[i]=f[i-1];
		if(pre[i]>=l){
			PII tmp=f[pre[i]-1];
			tmp.fi+=1;
			f[i]=f[i]+tmp;
		}
	}
	return f[r];
}
signed main(){
	freopen("arc.in","r",stdin);
	freopen("arc.out","w",stdout);
	n=read(); n*=3;
	for(int i=1;i<=n;i++){ 
		a[i]=read(),a[i+n]=a[i];
		if(a[i]==1) t[++t[0]]=i; 
	} 
	PII ans=solve(t[2]+1,t[1]+n-1) + solve(t[3]+1,t[2]+n-1) + solve(t[1]+1,t[3]-1);
	if(ans.fi==n/3-1)  printf("%lld\n",ans.se);
	else puts("0");
	return 0;
}

88.歸并

題面

定義對 $k$ 個長度為 $n$ 的序列的歸并為執(zhí)行以下操作 $kn$ 次后得到的序列 $A$：每次取出某個非空序列的開頭并放入 $A$ 的末尾。
兩個歸并不同當且僅當某一次操作不同。
我們稱一個歸并是合法的，當且僅當其中不存在長度為 $k$ 的子串滿足這個子串中的數(shù)全部相同。
現(xiàn)在給定 $m$ 個長度為 $n$ 的排列，排列的編號從 $1$ 到 $m$。
設(shè) $f(l,r)$ 表示只考慮編號在 $[l,r]$ 中的排列，他們的合法歸并的個數(shù)。
你需要求出 $\sum_{i=1}^m \sum_{j=i+1}^m f(i,j)$。

保證數(shù)據(jù)隨機生成。

數(shù)據(jù)范圍： $n,m\le 300$。

題解

先考慮對單個問題的求解，即如何求 $f(1,m)$。
設(shè) $f_i$ 表示當前歸并出的序列 $A$ 末尾第一次出現(xiàn) $m$ 個 $a_{1,i}$ （即第一個排列的第 $i$ 個數(shù)），且前面都合法的方案數(shù)（不去管后面的方案，也不去管那些 $a_{1,i}$ 的相對順序）。
轉(zhuǎn)移時先求總方案數(shù)，即前面隨便填（但要滿足每個排列是一個一個填的），只要滿足末尾有 $m$ 個 $a_{1,i}$ 即可，計算這個的話就是：$\frac {(\sum cnt_j)!}{\prod cnt_j!}$ 。
$cnt_j$ 表示第 $j$ 個排列 $a_{1,i}$ 前面有多少個數(shù)。
假設(shè)有一個 $j$ 可以轉(zhuǎn)移到 $i$，那么可以想到肯定是用 (總方案數(shù)) - $f_j \times $ (某些系數(shù))，即要去掉 $a_{1,j}$ 在 $a_{1,i}$ 之前就出現(xiàn)了 $m$ 次的情況。
這個系數(shù)的話就是 $m! \times \frac{(\sum s_k)!}{\prod s_k!}$。
其中 $m!$ 表示的是那 $m$ 個 $a_{1,j}$ 的順序要確定，然后 $s_k$ 表示第 $k$ 個排列的 $a_{1,j}$ 和 $a_{1,i}$ (不包括兩端) 之間的數(shù)的個數(shù)，$m!$ 后面那個式子意義類似于總方案那個式子。
然后 $j$ 能轉(zhuǎn)移到 $i$ 當且僅當在每個排列中 $a_{1,j}$ 都在 $a_{1,i}$ 前面。
我們可以在每個排列后面加一個 $n+1$，這樣 $f_{n+1}$ 的意義其實就是答案了(因為我們不去考慮最后那 $m$ 個相同數(shù)的順序)。
這樣求一次是 $O(n^2m)$，因為我們需要枚舉 $i$，再枚舉 $j$，再對每個排列判斷。

優(yōu)化的話順序枚舉 $l$，再從 $l$ 開始枚舉 $r$，求出 $[l,r]$ 里的排列的答案。
考慮對每個 $r$，用一個 vector 記錄對于每一個 $i$，能轉(zhuǎn)移到他的 $j$，以及對應(yīng)的系數(shù)，在最后統(tǒng)一轉(zhuǎn)移即可。

注意到數(shù)據(jù)隨機生成，所以一個排列里數(shù)字 $x$ 在 $y$ 前的概率是 $\frac{1}{2}$，即隨著 $r$ 的增大 $j$ 能轉(zhuǎn)移到 $i$ 的概率越小。
那么在 $r$ 右移時 $j$ 能轉(zhuǎn)移到 $i$ 的總次數(shù)的期望就是 $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} +...= O(1)$。
也就是說對于每個 $l$，總共的轉(zhuǎn)移次數(shù)期望是 $O(n^2)$ 的。

時間復(fù)雜度 $O(mn^2)$。

code

#include<bits/stdc++.h>
#define int long long 
#define PII pair<int,int>
#define fi first
#define se second 
using namespace std;
const int N=3e2+5,M=1e6+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int m,n,a[N][N],inv[M],q[M],fact[M],f[N],ans;
int pos[N][N];  //pos[i][x] 表示排列 i 中 x 的位置 
PII g[N];  //表示算每個 i 的總方案的系數(shù) 
struct P{
	int j,t1,t2,t3; //分別表示 j,m!,Σs[k],Π(s[k]!) 
};
vector<P> v[N];  
signed main(){
	freopen("merge.in","r",stdin);
	freopen("merge.out","w",stdout);
	m=read(),n=read()+1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<n;j++){
			a[i][j]=read();
			pos[i][a[i][j]]=j;
		}
		pos[i][n]=n;
		a[i][n]=n;  //在結(jié)尾加入 n+1 
	}
	
	inv[1]=1;
	for(int i=2;i<M;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	fact[0]=1;
	for(int i=1;i<M;i++) fact[i]=fact[i-1]*i%mod;
	q[0]=1;
	for(int i=1;i<M;i++) q[i]=q[i-1]*inv[i]%mod;
	
	for(int l=1;l<=m;l++){
		for(int i=1;i<=n;i++) v[i].clear();
		for(int i=1;i<=n;i++){
			g[i].fi=i-1 , g[i].se=q[i-1]; 
			for(int j=1;j<i;j++){
				v[i].push_back({j , 1 , i-j-1 , q[i-j-1]});
			}
		} 
		for(int r=l;r<=m;r++){
			for(int i=1;i<=n;i++){
				f[i] = fact[ g[i].fi ] * g[i].se % mod;
				for(P x:v[i]){
					f[i] = (f[i] - f[x.j] * x.t1 % mod * fact[x.t2] % mod * x.t3 % mod + mod) % mod ;		
				}				
			}
			(ans += f[n]) %= mod;  //r=l 時答案肯定是 0
			for(int i=1;i<=n;i++){   //加入 r+1 排列，更新可以轉(zhuǎn)移到 i 的 j。 
				int u=a[l][i];
				( g[i].fi += pos[r+1][u]-1 ) %= mod;
				( g[i].se *= q[pos[r+1][u]-1] ) %= mod;
				vector<P> tmp;
				for(P x:v[i]){
					int j=x.j,v=a[l][j];
					if(pos[r+1][v] < pos[r+1][u]){
						tmp.push_back({j , x.t1*(r+1-l+1)%mod , (x.t2+(pos[r+1][u]-pos[r+1][v]-1))%mod , x.t3*q[ pos[r+1][u]-pos[r+1][v]-1 ]%mod});
					}
				}
				swap(v[i],tmp);  //把 tmp 復(fù)制到 v[i] 
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

89.[ARC114C] Sequence Scores

操作肯定是先搞點小的位置再搞定大的位置。

考慮在 $A$ 的末尾 $pos$ 位置加一個 $x$ 會產(chǎn)生什么影響:

如果 $x$ 是第一次出現(xiàn)，那顯然 $ans+1$。
如果 $lst<i<pos$ 的 $a_i$ 都 $>x$，$ans$ 是不變的。
如果 $lst<i<pos$ 的 $a_i$ 有一個 $<x$，$ans+1$。

$lst$ 表示上一個 $x$ 出現(xiàn)的位置。

設(shè) $f_{i,x}$ 表示在第 $i$ 個位置放 $x$，在所有可能的情況中對答案產(chǎn)生的影響的和。
那么 $f_{i,x} = m^{i-1} - \sum_{k<i} m^{k-1} \times (m-x)^{i-k-1}$。
預(yù)處理后面那個東西就可以 $O(n^2)$ 了。

算答案時設(shè) $ans_i$ 表示前 $i$ 個位置的答案，那么 $ans_i=\sum_{x=1}^m ans_{i-1}+f_{i,x}$。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e3+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,g[N][N],f[N][N],ans[N];
int mi[N][N];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=0;i<=m;i++){
		mi[i][0]=1;
		for(int j=1;j<=n;j++) mi[i][j]=mi[i][j-1]*i%mod;
	}
	for(int i=2;i<=n;i++){
		for(int x=1;x<=m;x++){
			g[i][x] = (g[i-1][x]*(m-x)%mod + mi[m][i-2])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int x=1;x<=m;x++){
			f[i][x] = (mi[m][i-1] - g[i][x] + mod)%mod;
			(ans[i] += (ans[i-1]+f[i][x])%mod)%=mod;
		}
	}
	printf("%lld\n",ans[n]);
	return 0;
}

90.[ARC114D] Moving Pieces on Line

首先一個棋子不會走回頭路，他選好終點后就直接到終點了。

首先區(qū)間取反，可以認為是區(qū)間異或，區(qū)間異或再轉(zhuǎn)換為差分，改變判定條件：記 $flag_i$ 表示 $i$ 點左右兩邊的邊顏色是否相同，那么一次匹配 $(a_i,b_i)$ ($a_i$為起點，$b_i$為終點)，相當于把 $flag_{a_i}\oplus 1,flag_{b_i}\oplus 1$。
最終要求:每個 $flag_{t_i}=true$。

首先我們可以計算出哪些點要被操作奇數(shù)次，記它們?yōu)?$c_1,c_2...,c_m$, 操作定義為選他為終點。
具體的計算方法就是，一開始先把 $a_i$ 和 $t_i$ 都 $\oplus 1$，那么場上此時 $flag=1$ 的點就是要被操作奇數(shù)次的。
也就是說并不是所有的 $t_i$ 都要被操作奇數(shù)次，比如一個 $t_i$ 上放了一個棋子時。
也不是所有不是 $t_i$ 的都不能被操作奇數(shù)次，比如第一個樣例。
再次注意，一次操作指的是以他為終點，而不是起點。

一次匹配的代價是 $|b_i-a_i|$。
然后分類討論。

$n=m$ 時，直接分別排序，兩兩匹配即可。
$n<m$ 時，顯然無解。
$n>m$ 相當于分配多余的棋子去操作一些點偶數(shù)次，實際意義就是這兩個棋子相遇，即代價是 $|a_i-a_j|$，顯然 $|j-i|=1$ 即相鄰時最優(yōu)。
所以考慮 DP,設(shè) $f_{i,j}$ 表示前 $i$ 個棋子匹配前 $j$ 個 $c$ ，且必須匹配完（即需要考慮多余棋子）的最小代價。
轉(zhuǎn)移你就按照第 $i$ 個棋子是去匹配 $c_j$ 還是 $a_{i-1}$ 即可。

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e4+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k,a[N],t[N],c[N],m,flag[N],f[5005][5005];
int dis[N],cnt;
int Dis(int x){
	return lower_bound(dis+1,dis+cnt+1,x)-dis;
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i]=read(),dis[++cnt]=a[i];
	for(int i=1;i<=k;i++) t[i]=read(),dis[++cnt]=t[i];
	sort(dis+1,dis+cnt+1);
	sort(a+1,a+n+1);
	cnt=unique(dis+1,dis+cnt+1)-dis-1;
	for(int i=1;i<=n;i++) a[i]=Dis(a[i]),flag[a[i]]^=1;
	for(int i=1;i<=k;i++) t[i]=Dis(t[i]),flag[t[i]]^=1;
	for(int i=1;i<=cnt;i++) if(flag[i]) c[++m]=i;
	if(n<m) puts("-1");
	else if(n==m){
		int ans=0;
		for(int i=1;i<=n;i++){
			ans+=abs(dis[c[i]]-dis[a[i]]);
		}
		printf("%lld\n",ans);
	} 
	else{
		memset(f,0x3f,sizeof f);
		f[0][0]=0; 
		for(int i=1;i<=n;i++){
			for(int j=0;j<=m;j++){
				if(i==1&&j>=1) f[i][j]=f[i-1][j-1]+abs(dis[c[j]] - dis[a[i]]);
				else if(i>=2&&j==0) f[i][j]= f[i-2][j]+abs(dis[a[i]] - dis[a[i-1]]);
				else if(i>=2&&j>=1) f[i][j]=min(f[i-1][j-1]+abs(dis[c[j]]-dis[a[i]]) , f[i-2][j]+abs(dis[a[i]] - dis[a[i-1]]));		
			}
		}
		printf("%lld\n",f[n][m]);
	}
	return 0;
}

posted @ 2024-12-31 08:01 Green&White 閱讀(35) 評論(0) 收藏舉報

刷新頁面返回頂部

OIer_Cyq

動態(tài)規(guī)劃題單3

61.[CEOI2020] 星際迷航

code

62.[NOI Online #1 入門組] 跑步

code

63.CF1220E Tourism

code

64.采集

題目描述

題解

code

65.[ABC214G] Three Permutations

code

66.[NOI Online #2 提高組] 游戲

code

67.CF1895F Fancy Arrays

code

68.[ARC162E] Strange Constraints

code

69.[ARC163D] Sum of SCC

code

70.CF1728G Illumination

code

71.[ARC162D] Smallest Vertices

code

72.[ABC306Ex] Balance Scale

code

73. [TJOI2018] 游園會

code

74.開心消消樂

題面

題解

code

75. P1654 OSU!

code

76. Fluorescent

題意

題解

code

77. P3239 [HNOI2015] 亞瑟王

code

78.P3600 隨機數(shù)生成器

code

79.CF1151F Sonya and Informatics

code

80. CF1737E Ela Goes Hiking

code

81.[IOI 2008] Island

code

82.不條理狂詩曲

code

83.Sum

code

84. [PA 2021] Od deski do deski

code

85.Divan and Kostomuksha (hard version)

code

86.小 Y 和恐怖的奴隸主

code

87.阿兒克

題面

題解

code

88.歸并

題面

題解

code

89.[ARC114C] Sequence Scores

code

90.[ARC114D] Moving Pieces on Line

code

公告