「动态规划 2022/02 」学习记录

300iq Contest 3 H Horrible Cycles

给一个 \(2n\) 个点的二分图，左边第 \(i\) 个点向右边前 \(a_i\) 个点连边，求图中的简单环个数。

其中 \(n \le 5000\) 。

考虑对 \(2n\) 个点排序，使得对于每个左部点都会和前面的右部点连边。考虑每次先编号右部点然后删掉，如果出现一个左部点没有连边那么再给这个左部点标号。

考虑把环拆成链来计算，因为后面的点一定会连到前面的点。设 \(f(i,j)\) 表示对于前 \(i\) 个点，形成 \(j\) 条链的方案数。初始时 \(f(0,0)=1\) 。

如果 \(i\) 是右部点，由于排序所以他和前面都没有连边，所以他可以自己成链。

如果 \(i\) 是左部点，那么他和前面所有的右部点都有连边，所以他会把之前的两条合并到一条。

最后答案要减去二元环的情况，减去所有边即可。然后将答案除以 \(2\) ，因为考虑链的时候是考虑顺序的。

Atcoder CF2017ETR3 F Unicyclic Graph Counting

求 \(n\) 个点的基环树个数，满足第 \(i\) 个点的度数为 \(d_i\)。

其中 \(n \le 300\) 。

首先，如果不看环生成 prufer 序列，那么最后一定会剩下一个环和环旁边的一个点。

对于一个普通的树，如果第 \(i\) 个点度数是 \(d_i\) ，那么答案为 \(\dfrac{(n-2)!}{\prod{(d_i-1)!}}\) 。那么对于基环树，在树上的点就是 \(d_i-1\) 的 出现次数，环上的就是 \(d_i-2\) ，环上和环外的特殊点是 \(d_i-3\) 。

于是有答案 \(\dfrac{(n-|S|-1)!}{\prod(d_i-k)!}\) 。其中 \(k\) 是决定点的类型，\(S\) 是环的集合。

那我们考虑枚举环，但这样显然会 T 。因为同样大小的环本质相同，所以变成枚举环的大小。

于是变成要计算对于一个大小所有的环的 \(\prod(d_i-k)\) 贡献。

这部分考虑 DP ，设 \(f(i,j,k)\) 表示考虑前 \(i\) 个点，有 \(j\) 个在环上，已经有了 \(k=0/1\) 个特殊点。分类直接转移即可。

注意这个 DP 可以用分治 FFT 优化，但原题不需要我没写（？

以及因为 prufer 序列不考虑一个点的情况，所以需要特判只有一个大环的情况。

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll N=300+5;
const ll Mod=1e9+7;
ll n,ans,d[N],mul[N],inv[N],fmul[N],f[N][N][2];
int main()
{	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
		scanf("%lld",&d[i]);
	mul[0]=mul[1]=inv[0]=inv[1]=fmul[0]=fmul[1]=1;
	for(ll i=2;i<=n;i++)
	{	inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
		mul[i]=mul[i-1]*i%Mod,fmul[i]=fmul[i-1]*inv[i]%Mod;
	}
	bool is=1;
	for(int i=1;i<=n;i++)
		if(d[i]!=2)is=0;
	if(is==1)
	{	printf("%lld\n",mul[n-1]*inv[2]%Mod);
		return 0;
	}
	f[0][0][0]=1;
	for(ll i=1;i<=n;i++)
		for(ll j=0;j<=i;j++)
			for(ll k=0;k<2;k++)
			{	if(d[i]>=1)f[i][j][k]=(f[i][j][k]+f[i-1][j][k]*fmul[d[i]-1]%Mod)%Mod;
				if(d[i]>=2)f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*fmul[d[i]-2]%Mod)%Mod;
				if(d[i]>=3&&k)f[i][j][1]=(f[i][j][1]+f[i-1][j-1][0]*fmul[d[i]-3]%Mod)%Mod;
			}
	for(ll i=3;i<=n;i++)
		ans=(ans+f[n][i][1]*mul[n-i-1]%Mod*mul[i-1]%Mod*inv[2]%Mod)%Mod;
	printf("%lld\n",ans);
	return 0;
}

300iq Contest 1 J Jealous Split

给一个长度为 \(n\) 的序列，将其划分为 \(k\) 部分，记 \(s_i\) 表示第 \(i\) 部分的和，\(m_i\) 表示第 \(i\) 部分的最大值，构造这样一个划分使得：

\[\forall 1 \le i

其中 \(n \le 10^5\) 。

最后只需要构造，所以考虑一种不合法的情况怎么变成合法。

可以通过调整分界点，在相邻两块最大值不变的情况下，通过这个调整，只会出现和的差变小。那可以考虑维护每段的和的平方的和。

于是题目变成最小化每段和的平方的和，答案是关于 \(k\) 的凸函数，于是可以 wqs 二分。

Yandex Algorithm 2018 Final Round D LIS vs. LDS

给定一个排列，求一组不相交的 LIS 和LDS 。

其中 \(n \le 5 \times 10^5\)。

性质题。首先要发现一个性质，LIS 和 LDS 至多有一个交点。

不妨记 \(f_i\) 表示经过 \(i\) 的 LDS 个数，即从前往后跑 LDS 从后之前跑 LIS 的方案积，再记一个 \(S\) 表示 LDS 总和。

考虑一个 LIS 什么时候一定不合法，也就是不存在一个 LDS 和他没有交点。也就是对于一组 LIS \(\{ i_1,i_2,...,i_k \}\) ，满足其 \(\sum\limits_{j=1}^k f_{i_j}=S\) ，那么一定不合法。

所以只要找一个不满足这个条件的 LIS 即可。

不妨找两个 LIS ，使他们的 \(f\) 和不同，这样最多有一个不合法。

因为这个数字可能很大，所以考虑对一个大质数取膜来优化代码部分（

CF868F Yet Another Minimization Problem

将一个长度为 \(n\) 的序列分为 \(k\) 段，一段 \([l,r]\) 的代价是 \(l \le i < j \le r,a_i=a_j\) 的 \((i,j)\) 对数。最小化分割代价。

其中 \(n \le 10^5,k \le 20\) 。

先考虑暴力 DP ，设 \(f(i,j)\) 表示前 \(i\) 个分了 \(j\) 段的情况，设 \(\operatorname{calc}(k,i)\) 表示区间 \([k,i]\) 的贡献。于是显然有：

暴力 DP 过不去就是决策单调。

首先 \(\operatorname{calc}()\) 是单调的。

考虑决策点 \(x,y\) ，其中 \(x 。那么对于 \(i\) 右移前有 \(f(x-1,j-1)+\operatorname{calc}(x,i) > f(y-1,j-1)+\operatorname{calc}(y,i)\) 。那么右移后依然有。

于是决策单调。

因此我们考虑先枚举 \(k\) ，于是可以分治计算。计算每段的贡献类似用莫队的方法计算。 复杂度 \(\mathcal{O}(nk \log n)\) 。

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll N=2e5+5;
const ll inf=1e15;
ll n,m,sum,l,r,a[N],cnt[N],dp[N][25];
ll calc(ll L,ll R)
{	while(l>L)sum+=cnt[a[--l]]++;
	while(rR)sum-=--cnt[a[r--]];
	return sum;
}
void solve(ll L,ll R,ll x,ll y,ll dep)
{	ll mid=(L+R)>>1,pos,tl=max(1ll,x),tr=min(mid,y);
	ll mn=inf;
	for(ll i=tl;i<=tr;i++)
	{	ll val=dp[i-1][dep-1]+calc(i,mid);
		if(val