DP 时可行的某些套路。
I.DP 的图论化
将 DP 式子实际化有时会提供新思路。
这可以被看作是同一个 DP 式解决不同的问题，因此一定程度上考验出题的功夫。
I.[UOJ#76][UR#6]懒癌
现在考虑某一局面。
此时，考虑每只懒狗的主人。考虑其射杀懒狗的时间：其假定自己的狗不懒，考虑其观察不到的人的所有可能状态，得到了这些状态下枪响的最大时刻，然后发现直到这一时刻都没有枪响，那么下一时刻他就会干掉自己的狗。
于是我们发现一个人的决策仅与其看不到的人有关。那么我们考虑原图的补图。
发现，补图中若有两个懒狗的主人互相看不见，那么他们都不会开枪。
进而，如果补图中有两个懒狗的主人在同一个强连通分量中，也会一直持续下去——不妨假定该强连通分量是环，而某懒狗的主人在假定其看不到的人拥有懒狗时发现此时并不会有逻辑错误，即每个人都可以一直假定其看不到的人有懒狗。
进而，如果一个懒狗的主人能够走到一个大小大于一的强连通分量，他亦不会开枪。
于是我们发现可以删去强连通分量以及所有可达其的节点，因为任意时刻他们都不会开枪。
然后我们愉快地得到了一张 DAG。
这个时候我们考虑一个 DP，即设 \(f(\mathbb S)\) 表示 \(\mathbb S\) 集合中点是懒狗时的答案，则有
这个 DP 是非常显然的，其根据我们一开始就提到的“每个人的策略”而构建。
现在我们把这个 DP 放到 DAG 上。我们设“黑点”表示懒狗及被某个人认为可能是懒狗的集合。那么由 DP 的转移，我们每次可以删去一个黑点，并将所有其出边到达点染黑。因为 DP 式外面是 \(\min\)，所以我们删去的黑点必然是不会被再度染黑的点。这就表明上述流程执行的轮数就是开枪时刻。
进一步地，我们得到结论，所有能被黑点到达的点的数量就是首次开枪时间，且所有不被任何黑点到达的黑点数即为首次开枪数量。
统计一下：一个点不会贡献到时间中当且仅当所有可达它的点包括它自身都不是黑点；一个点会贡献到次数中当且仅当所有可达它的点都不是黑点，而它自己是黑点。
用 bitset 优化传递闭包什么的随便算算即可。时间复杂度 \(O(\dfrac{n^3}{\omega})\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int n,dis[3010],A,B,q[3010],m,in[3010];
char s[3010][3010];
bitset<3010>bs[3010];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%s",s[i]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j&&s[i][j]=='0')in[i]++;
for(int i=0;i<n;i++)if(!in[i])q[m++]=i;
for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(j!=q[i]&&s[j][q[i]]=='0'&&!--in[j])q[m++]=j;
for(int i=0;i<m;i++)for(int j=0;j<m;j++)if(s[q[i]][q[j]]=='0')bs[j].set(i);
for(int i=0;i<m;i++)for(int j=0;j<m;j++)if(bs[i].test(j))bs[i]|=bs[j];
for(int i=0,s;i<m;i++)s=m-bs[i].count(),A=(0ll+A+ksm(2,m)+mod-ksm(2,s))%mod,(B+=ksm(2,s))%=mod;
printf("%d %d\n",A,B);
return 0;
}
II.[GYM103409L]Wiring Engineering
一个显然的 DP 是设 \(f_{i,j}\) 表示仅考虑左部 \([a,i)\) 与右部 \([b,j)\) 中元素时的答案。要进行转移需要设 \(g_{i,j}\) 表示钦定左部的 \(i\) 被选以及 \(h_{i,j}\) 表示钦定右部的 \(j\) 被选的答案。
转移式子可以简单列出，我们发现式子与 \(a,b,c,d\) 事实无关。
怎么利用这个性质呢？我们将 \(f,g,h\) 数组各自写成点，转移写成边，则答案事实为 \(f_{a,c}\to f_{b+1,d+1}\) 的最长路。
考虑分治。假设分治中心是 \(m\)。考虑计算所有左部跨 \(m\) 的询问。对于所有询问必然都存在 \(j\) 满足 \(h_{m,j}\) 在最长路中。于是我们枚举 \(j\)，求出其到其它点的最长路即可。复杂度 \(O(n^3)\)。
轮流在左部和右部进行分治，有复杂度为 \(T(n)=4T(n/2)+O(n^3)\)。由 Master Theorem，这个复杂度是 \(O(n^3)\) 的。
总复杂度 \(O(n^3+qn)\)。
要注意常数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll fni=0x8f8f8f8f8f8f8f8f;
int n,q,u[510],v[510],w[510][510];
ll f[2][510][510],g[2][510][510],h[2][510][510];
int A[300100],B[300100],C[300100],D[300100],ord[300100],dro[300100],arr[300100];
ll res[300100];
void solvex(int,int,int,int,int,int);
void solvey(int,int,int,int,int,int);
void chmx(ll&x,ll y){if(x<y)x=y;}
void trans(int lx,int rx,int X,int ly,int ry,int Y){
for(int i=X;i>=lx;i--)for(int j=Y;j>=ly;j--){
chmx(f[0][i][j],g[0][i][j]-u[i]);
chmx(f[0][i][j],h[0][i][j]-v[j]);
if(i>lx){
chmx(f[0][i-1][j],f[0][i][j]),chmx(g[0][i-1][j],f[0][i][j]);
chmx(h[0][i-1][j],h[0][i][j]+max(0,w[i-1][j]-u[i-1]));
chmx(g[0][i-1][j],h[0][i][j]+w[i-1][j]-v[j]);
}
if(j>ly){
chmx(f[0][i][j-1],f[0][i][j]),chmx(h[0][i][j-1],f[0][i][j]);
chmx(g[0][i][j-1],g[0][i][j]+max(0,w[i][j-1]-v[j-1]));
chmx(h[0][i][j-1],g[0][i][j]+w[i][j-1]-u[i]);
}
}
for(int i=X;i<=rx+1;i++)for(int j=Y;j<=ry+1;j++){
if(i>X){
chmx(f[1][i][j],f[1][i-1][j]),chmx(f[1][i][j],g[1][i-1][j]);
chmx(h[1][i][j],h[1][i-1][j]+max(0,w[i-1][j]-u[i-1]));
chmx(h[1][i][j],g[1][i-1][j]+w[i-1][j]-v[j]);
}
if(j>Y){
chmx(f[1][i][j],f[1][i][j-1]),chmx(f[1][i][j],h[1][i][j-1]);
chmx(g[1][i][j],g[1][i][j-1]+max(0,w[i][j-1]-v[j-1]));
chmx(g[1][i][j],h[1][i][j-1]+w[i][j-1]-u[i]);
}
chmx(g[1][i][j],f[1][i][j]-u[i]);
chmx(h[1][i][j],f[1][i][j]-v[j]);
}
for(int i=1;i<=arr[0];i++)
chmx(res[arr[i]],f[0][A[arr[i]]][C[arr[i]]]+f[1][B[arr[i]]+1][D[arr[i]]+1]);
for(int i=lx;i<=rx+1;i++)for(int j=ly;j<=ry+1;j++)
f[0][i][j]=g[0][i][j]=h[0][i][j]=f[1][i][j]=g[1][i][j]=h[1][i][j]=fni;
}
void solvex(int lx,int rx,int ly,int ry,int L,int R){
if(L>R)return;
int m=(lx+rx)>>1;
arr[0]=0;
int LL=L-1,RR=R+1;
for(int i=L;i<=R;i++){
if(B[ord[i]]<m)dro[++LL]=ord[i];
else if(A[ord[i]]>m)dro[--RR]=ord[i];
else arr[++arr[0]]=ord[i];
}
// for(int i=1;i<=arr[0];i++)printf("%d ",arr[i]);puts("");
for(int k=ly;k<=ry+1;k++)h[0][m][k]=h[1][m][k]=0,trans(lx,rx,m,ly,ry,k);
for(int i=L;i<=LL;i++)ord[i]=dro[i];solvey(lx,m-1,ly,ry,L,LL);
for(int i=RR;i<=R;i++)ord[i]=dro[i];solvey(m+1,rx,ly,ry,RR,R);
}
void solvey(int lx,int rx,int ly,int ry,int L,int R){
if(L>R)return;
int m=(ly+ry)>>1;
arr[0]=0;
int LL=L-1,RR=R+1;
for(int i=L;i<=R;i++){
if(D[ord[i]]<m)dro[++LL]=ord[i];
else if(C[ord[i]]>m)dro[--RR]=ord[i];
else arr[++arr[0]]=ord[i];
}
// for(int i=1;i<=arr[0];i++)printf("%d ",arr[i]);puts("");
for(int k=lx;k<=rx+1;k++)g[0][k][m]=g[1][k][m]=0,trans(lx,rx,k,ly,ry,m);
for(int i=L;i<=LL;i++)ord[i]=dro[i];solvex(lx,rx,ly,m-1,L,LL);
for(int i=RR;i<=R;i++)ord[i]=dro[i];solvex(lx,rx,m+1,ry,RR,R);
}
namespace FIFO{
char buf[1<<23],*p1=buf,*p2=buf;
#define gc() getchar()
template<typename T>void read(T&x){
x=0;
char c=gc();
while(c>'9'||c<'0')c=gc();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc();
}
template<typename T>void print(T x){if(x<=9)putchar('0'+x);else print(x/10),putchar('0'+x%10);}
}using namespace FIFO;
int main(){
read(n),read(q);
for(int i=1;i<=n;i++)read(u[i]);
for(int i=1;i<=n;i++)read(v[i]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)read(w[i][j]);
for(int i=1;i<=q;i++)read(A[i]),read(B[i]),read(C[i]),read(D[i]),ord[i]=i;
memset(f,fni,sizeof(f)),memset(g,fni,sizeof(g)),memset(h,fni,sizeof(h));
solvex(1,n,1,n,1,q);
for(int i=1;i<=q;i++)print(res[i]),putchar('\n');
return 0;
}
III.CF1616G Just Add an Edge
记 \(x\to y\) 表示 \(x\) 到 \(y\) 的边。
考虑 \(x\to y\)（其中 \(x>y\)）的边被连上时，存在哈密顿路径的条件。
-------------- --------------------
| | | |
| v | v
1->2->...->(x-2)->(x-1) x (x+1) (x+2) ... (y-2) (y-1) y (y+1)->(y+2)->...->(n-1)->n
| ^ | ^ | ^ | ^
| | | | | | | |
---- --------------- ----- -------
如图，记 \(x\Rightarrow y\) 表示在原图中存在 \(x\to(x+1)\to(x+2)\to\dots\to(y-1)\to y\) 的路径。
则应满足 \(1\Rightarrow(x-1)\) 且 \((y+1)\Rightarrow n\)，且 \(\left<(x-1),x\right>\) 的元组分别能够到达 \(\left<y,(y+1)\right>\)。
前两条限制的判定是简单的，关键是最后一条。
设 \(f_{i,j}\) 表示两条路径的端点分别是 \(i,j\) 时的态。则我们就要从 \(f_{x-1,x}\) 转移到 \(f_{y,y+1}\)。假如将转移写成边，则只需判断两者是否可达即可。用 \(\rightsquigarrow\) 表示该可达关系。
现在考虑转移。显然建出全体点和边的操作是不现实的。但我们可以只保留 \(|i-j|=1\) 的点。具体而言，考虑 \(f_{i,j}\) 的转移（不妨假设 \(i<j\)）。则其必然是 \(j\) 先不断加一地转移到 \(k\) 态，接着 \(i\) 转移到 \(k+1\)。具体而言，若 \(f_{i,j}\to f_{k+1,k}\)，则必有 \(i\to(k+1)\) 且 \(j\Rightarrow k\)。
\(i\to(k+1)\) 的 \((i,k)\) 数量总共只是 \(O(m)\) 的，\(j\Rightarrow k\) 可以用前缀和之类 \(O(1)\) 判定。故建图是 \(O(n+m)\) 的。
考虑满足 \(1\Rightarrow l\) 的最大 \(l\)，同理有 \(r\Rightarrow n\) 的最小 \(n\)。若 \(l=n\) 且 \(r=1\)，这意味着原图即存在哈密顿路径，则无论加入何种边都是合法的，故答案即为 \(\dbinom n2\)。
否则，必有 \(l<r\)。则对于 \(x\leq l+1\) 且 \(r-1\leq y\) 且 \(x<y\) 的 \((x,y)\) 对，若 \(f_{x-1,x}\rightsquigarrow f_{y,y+1}\)，则合法。
注意到因为不存在 \(l\to(l+1)\) 和 \((r-1)\to r\) 的边，所以 \(f_{l,l+1}\) 和 \(f_{r-1,r}\) 的态事实上是“必经”的。故只需首先判定是否有 \(f_{l,l+1}\rightsquigarrow f_{r-1,r}\)，然后再找出所有可达 \(f_{l,l+1}\) 的位置和所有被 \(f_{r-1,r}\) 可达的位置即可。复杂度线性。
实际使用时，只需用 \(l\) 即可。
需要特别注意的是 \(x=1\) 或 \(y=n\) 的情形。解决方法之一是新增一个 \(0\) 连到所有点和一个 \(n+1\) 被所有点连到。这样，\(x=1\) 时只需考虑 \(f_{0,1}\) 即可，\(y=n\) 时考虑 \(f_{n,n+1}\) 亦可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,a[150100],rp[150100];
int f[150100][2];
vector<int>v[150100];
void mina(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++)v[i].clear(),a[i]=0;
for(int i=2;i<=n;i++)v[0].push_back(i);
for(int i=1;i<n;i++)v[i].push_back(n+1);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
if(x+1==y)a[x]=true;
else v[x].push_back(y);
}
int l=1,r=n;
while(l<n&&a[l])l++;
while(r>1&&a[r-1])r--;
if(l==n&&r==1){printf("%lld\n",1ll*n*(n-1)>>1);return;}
rp[n+1]=n+1;for(int i=n;i;i--)rp[i]=(a[i]?rp[i+1]:i);
memset(f,0,sizeof(f));
f[l][0]=1,f[l][1]=2;
for(int i=l;i<=n+1;i++)for(auto j:v[i])
if(rp[i+1]>=j-1)for(int k=0;k<2;k++)f[j-1][k]|=f[i][!k];
for(int i=l;i>=0;i--)for(auto j:v[i])
if(rp[i+1]>=j-1&&j-1<=l)for(int k=0;k<2;k++)f[i][k]|=f[j-1][!k];
int c[4],d[4];memset(c,0,sizeof(c)),memset(d,0,sizeof(d));
for(int i=0;i<=l;i++)c[f[i][0]]++;
for(int i=r-1;i<=n;i++)d[f[i][0]]++;
ll res=0;
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(i&j)res+=1ll*c[i]*d[j];
printf("%lld\n",res-(l+1==r));
}
int main(){
scanf("%d",&T);
while(T--)mina();
return 0;
}
II.网格图化后状压 DP
常常见到一类问题，诸如“\(x+1\) 与 \(x+m\) 不能共存，求 \(1\sim n\) 中所有数保留的方案数”。此时，可以把不能共存的关系写成网格图。这样，网格图的较短边长只有 \(\sqrt n\) 级别，往往就可以状压了。
I.[HNOI2012]集合选数
考虑 \(1\)，其不能与 \(2\) 和 \(3\) 共存；\(2\) 不能与 \(6\) 与 \(4\) 共存，\(3\) 则是 \(6\) 与 \(9\)……
于是发现我们可以建立一个网格图：
1 2 4 8 16
3 6 12 24 48
9 18 36 72 144
27 54 108 216 432
其中每个数 \(x\) 右侧是 \(2x\)，下方是 \(3x\)。发现该图的两两相邻位置均不能同时选择。并且，该图最多有 \(\log_3n\) 行、\(\log_2n\) 列。可以直接状压解决。
但是，上图仅考虑了前 \(n\) 个数中仅包含 \(2,3\) 作为因子的全部数；于是我们还要枚举所有并非 \(2,3\) 倍数的数填到左上角形成矩阵，然后DP出每个矩阵的结果再乘一起即可。
时间复杂度 \(O(\text{能过})\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+1;
int n,f[20][1<<12],len[18],res=1;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
if(!(i%2)||!(i%3))continue;
int m=0;
for(int k=i;k<=n;k<<=1,m++){
len[m]=0;
int j=n/k;
while(j)len[m]++,j/=3;
}
for(int j=0;j<(1<<len[0]);j++)f[0][j]=((j&(j<<1))==0);
for(int j=1;j<m;j++)for(int l=0;l<(1<<len[j]);l++){
f[j][l]=0;
if(l&(l<<1))continue;
for(int k=0;k<(1<<len[j-1]);k++)if((k&(k<<1))==0&&(l&k)==0)(f[j][l]+=f[j-1][k])%=mod;
}
res=1ll*res*(f[m-1][0]+f[m-1][1])%mod;
}
printf("%d\n",res);
return 0;
}
III.贪心优化背包
对于某些特殊的背包问题，可以通过贪心加以优化。
I.[GYM102822I]Invaluable Assets
引理1.最优解法下我们会尽量选取效果为 \(\sqrt{c}\) 的肥料。
考虑每袋肥料单位效果所需费用——此为 \(\dfrac{x^2+c}{x}\)。将分数拆开并套上均值，得到最大值在 \(\sqrt{c}\) 处取到。但因为肥料只能选取整数值，所以我们找到其上取整和下取整中更优的一个作为最值，设其为 \(p\)。则，从 \(1\sim p-1\)，单位费用不增；从 \(p+1\sim\infty\)，单位费用不降。（考虑对勾函数的图像即可）
引理2.最优解法中不会使用效果大于等于 \(2p\) 的肥料。
显然，对于一个效果大于等于 \(2p\) 的肥料，从中拆出一包肥料单独以 \(p\) 的效果使用，单位费用减少了；因此最多只会使用效果小于 \(2p\) 的肥料。
引理3.至多使用两种不同肥料。
考虑假设我们有两包肥料 \(i,j\) 在最优方案中被使用，则一定可以通过把它们各自向中间移动一位使得单位费用减少（因为对勾函数是凹函数）。不断移动，最终会得到结论——我们最多只会使用两种不同肥料，且其效果相差 \(1\)。
引理4.不存在若干个和为 \(p\) 倍数的肥料。
这很显然，因为你明显可以用很多包 \(p\) 肥料来代替。
引理5.选择的非 \(p\) 肥料的费用不大于 \(3c\)。
结合引理2、3、4，我们会发现，我们最多选择 \(p-1\) 个小于 \(2p\) 的不同非 \(p\) 肥料（不然必存在和为 \(p\) 倍数的肥料组）。\((p-1)(2p-1)\leq3c\) 是一定成立的。
则我们考虑暴力背包求出需要肥料总量不大于 \(3c\) 的最优费用。依照上述结论，共有 \(2p-1\) 种不同物品，此部分复杂度 \(O(pc)=O(c\sqrt{c})\)。
现在，考虑回答询问。假设对于一次询问，有一棵树需要生长 \(k\) 单位，则若 \(k\leq3c\)，显然我们可以直接通过DP数组回答；否则，考虑找出与 \(k\) 关于 \(p\) 同余且不大于 \(3c\) 的最大数，则答案即为该数的DP值+剩余部分全部用 \(p\) 填充的费用。
考虑将所有询问按照模 \(p\) 的余数分到 \(p\) 个同余类里，并在每个同余类中通过扫描线维护答案。因为数据随机，所以此部分也可以通过。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,q,p,f[30100],h[100100],lim[100100],equ[110],cost;
ll res[100100];
vector<int>v[10100];
ll query(int now,int las){
ll ret=0;
int l1=lower_bound(h+1,h+n+1,now)-h;
int l2=lower_bound(h+1,h+n+1,las-2*m)-h;
for(int i=l2;i<l1;i++){
int tmp=now-h[i];
if(tmp<=3*m)ret+=f[tmp];
else ret+=f[equ[tmp%p]]+1ll*(tmp-equ[tmp%p])/p*cost;
if(h[i]<=las)ret-=f[las-h[i]];
}
ret+=1ll*((now-las)/p)*cost*(l2-1);
return ret;
}
int main(){
scanf("%d",&T);
for(int tt=1;tt<=T;tt++){
scanf("%d%d%d",&n,&m,&q),p=sqrt(m);
if((p*p+m)*(p+1)>((p+1)*(p+1)+m)*p)p++;
// printf("%d\n",p);
cost=p*p+m;
memset(f,0x3f,sizeof(f)),f[0]=0;
for(int i=1;i<=2*p;i++)for(int j=i;j<=3*m;j++)f[j]=min(f[j],f[j-i]+i*i+m);
// for(int i=0;i<=3*m;i++)printf("%d ",f[i]);puts("");
for(int i=1;i<=n;i++)scanf("%d",&h[i]);sort(h+1,h+n+1);
// for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
for(int i=1;i<=q;i++)scanf("%d",&lim[i]),v[lim[i]%p].push_back(i);
for(int i=m-p+1;i<=m;i++)equ[i%p]=i;
for(int i=0;i<p;i++){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end(),[](int x,int y){return lim[x]<lim[y];});
res[v[i][0]]=query(lim[v[i][0]],0);
for(int j=1;j<v[i].size();j++)res[v[i][j]]=res[v[i][j-1]]+query(lim[v[i][j]],lim[v[i][j-1]]);
v[i].clear();
}
printf("Case #%d:\n",tt);
for(int i=1;i<=q;i++)printf("%lld\n",res[i]);
}
return 0;
}
II.[ARC096D] Sweet Alchemy
首先先差分一下。然后问题可以转化为，有 \(n\) 个物品，第 \(i\) 个物品的收益是 \(w_i\)，代价是 \(v_i\)，且除了 \(1\) 以外其它物品都只能选至多 \(d\) 个的背包问题。
考虑一个错误的贪心，即按照 \(\dfrac{v_i}{w_i}\) 排序，选择此值最小的一些。
因为 \(w\) 只有 \(n\) 的范围，所以对于 \(i,j\) 两个元素，假如 \(i\) 比 \(j\) 优，则可以将 \(w_i\) 次 \(j\) 换成 \(w_j\) 次 \(i\)，所以 \(j\) 仅会选用不超过 \(n\) 次。那么我们就将前 \(n\) 个元素扔到背包里，然后剩下的元素贪心就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,p,d,s[60],fa[60],c,ord[60],mx;
ll m[60],f[200100];
void ins(int w,ll v){for(int i=n*n*c;i>=w;i--)f[i]=min(f[i],f[i-w]+v);}
int main(){
scanf("%d%d%d",&n,&p,&d),c=min(n,d),d-=c;
scanf("%lld",&m[1]),s[1]=1;
for(int i=2;i<=n;i++)scanf("%lld%d",&m[i],&fa[i]);
for(int i=n;i>=2;i--)s[fa[i]]+=++s[i],m[fa[i]]+=m[i];
// for(int i=1;i<=n;i++)printf("%d %d\n",s[i],m[i]);
memset(f,0x3f,sizeof(f)),f[0]=0;
for(int i=1;i<=n;i++){
int t=c;
for(int j=1;j<=t;t-=j,j<<=1)ins(s[i]*j,m[i]*j);
ins(s[i]*t,m[i]*t);
}
for(int i=1;i<=n;i++)ord[i]=i;
sort(ord+1,ord+n+1,[](int i,int j){return m[i]*s[j]<m[j]*s[i];});
for(int i=0;i<=n*n*c;i++){
if(f[i]>p)continue;
// printf("%d,%d\n",i,f[i]);
int rem=p-f[i],val=i;
for(int j=1;j<=n;j++){
int k=ord[j];
int now=min(rem/m[k],(ll)(k!=1?d:0x3f3f3f3f));
val+=now*s[k],rem-=now*m[k];
}
mx=max(mx,val);
}
printf("%d\n",mx);
return 0;
}
IV.二项式系数写入状态
对于一些题目，把式子写成二项式系数会让 DP 更高效。
I.净土裁断
题意：
给定一棵 \(1\) 为根的树。每个点上有整数 \(p_i\)，表示如果当前时刻在 \(i\)，则有 \(\dfrac{p_i}{10^6}\) 的概率停在原地不动，\(1-\dfrac{p_i}{10^6}\) 的概率等可能地向某个与其相邻的点游走一步。
对每个点求出其首次游走至 \(1\) 的时间的 \(k\) 次幂的期望，对 \(998244353\) 取模。
数据范围：\(nk\leq10^6,n\leq10^5,0\leq k\leq10^3,0\leq p_i<10^6\)。
首先将 \(p\) 除去 \(10^6\) 得到概率。
首先，当 \(k=1\) 时，套路之一是设 \(f_i\) 表示从节点 \(i\) 出发向父亲游走一步的期望时间。则 \(f_i=\Big(\sum\limits_{j\text{ is a son of }i}f_j+\dfrac{1}{1-p_i}\Big)+\dfrac{1}{1-p_i}\)。
但是这个做法在 \(k>1\) 时不具有扩展性，因为 \(k>1\) 时的理论基础是二项式定理 \((x+y)^k=\sum\limits_{i=0}^k\dbinom kix^iy^{k-i}\) 在期望下的形式 \(\text E\Big((x+y)^k\Big)=\sum\limits_{i=0}^k\dbinom ki\text E(x^i)\text E(y^{k-i})\)，其中 \(\text E\) 表示期望。上述做法最后每个点的答案是至根的路径求和，但是路径求和在二项式定理下就成为了路径卷积，复杂度不可避免地要是 \(nk\log k\)，一看就不太靠谱。
因此我们只能考虑其它的 DP 方法，比如设 \(f_i\) 表示从节点 \(i\) 出发游走到 \(1\) 的期望时间。
使用树上高斯消元，可以列出式子
现在设 \(f_{i,k}\) 表示 \(k\) 次幂时的答案，套用二项式定理，得到
按照 \(k\) 分层 DP，这样子前面层的结果就可以被看作常数，进而有一个 \(nk^2\) 的做法。
怎么优化呢？考虑用下降幂展开常规幂。
下降幂不好处理，但是组合数可以使用杨辉三角递推式处理。于是我们将上式变为
然后只需令 \(f_{i,k}\) 表示路径长度 \(l\) 的 \(\dbinom lk\) 的期望。转移的时候使用 \(\dbinom lk=\dbinom{l-1}{k-1}+\dbinom{l-1}k\)，得到式子
然后分层消元即可。时间复杂度 \(O(nk)\)。
需要特判 \(k=0\) 的情形。
初态为 \(f_{i,0}=1\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
const int MIL=ksm(1000000);
int n,m,f[100100],g[100100],p[100100],sti[1010][1010],fac[1010];
int K[100100],B[100100];
vector<int>v[100100];
void dfs1(int x,int fa){
int sel=p[x],q=1ll*(1+mod-p[x])*ksm(v[x].size())%mod;
K[x]=q,B[x]=1ll*f[x]*p[x]%mod;
for(auto y:v[x]){
if(y!=fa)dfs1(y,x),sel=(1ll*K[y]*q+sel)%mod,B[x]=(1ll*B[y]*q+B[x])%mod;
B[x]=(1ll*f[y]*q+B[x])%mod;
}
sel=ksm((1+mod-sel)%mod);
K[x]=1ll*K[x]*sel%mod,B[x]=1ll*B[x]*sel%mod;
}
void dfs2(int x,int fa){for(auto y:v[x])if(y!=fa)f[y]=(1ll*K[y]*f[x]+B[y])%mod,dfs2(y,x);}
int main(){
freopen("raiden.in","r",stdin);
freopen("raiden.out","w",stdout);
scanf("%d%d",&n,&m);
if(m==0){for(int i=2;i<=n;i++)puts("1");return 0;}
sti[0][0]=1;
for(int i=1;i<=m;i++)for(int j=1;j<=i;j++)sti[i][j]=(1ll*j*sti[i-1][j]+sti[i-1][j-1])%mod;
// for(int i=1;i<=m;i++){for(int j=1;j<=i;j++)printf("%d ",sti[i][j]);puts("");}
fac[0]=1;for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for(int i=2;i<=n;i++)scanf("%d",&p[i]),p[i]=1ll*p[i]*MIL%mod;
for(int i=1;i<=n;i++)f[i]=1;
for(int i=1;i<=m;i++){
dfs1(1,0),f[1]=0,dfs2(1,0);
// for(int j=2;j<=n;j++)printf("%d ",f[j]);puts("");
for(int j=2;j<=n;j++)g[j]=(1ll*sti[m][i]*fac[i]%mod*f[j]+g[j])%mod;
}
for(int i=2;i<=n;i++)printf("%d\n",g[i]);
return 0;
}
II.斐波那契
题意：给定 \(a,b\)，定义包含 \(x\) 个
0和 \(y\) 个1的01序列的权值等于 \(x^ay^b\)。对于长度为 \(n\) 的全体不存在相邻1的01序列，求其权值和。数据范围：\(0\leq a,b\leq200,1\leq n\leq10^{18}\)。
本题的方法很多。但是没有一种使用了题目名称“斐波那契”的。
所以它为什么叫“斐波那契”呢？因为不相邻
01串与自然数存在一一映射（即齐肯多夫表示法）。但是说实话没用罢了。
Algorithm 1.BM。
盲猜这是低阶线性递推式，具体是 \(4(a+b)+O(1)\) 阶的式子。暴力 \((a+b)^3\) 地 DP 出前 \(O(a+b)\) 项后直接 BM+常系数齐次线性递推即可。复杂度 \(O\Big((a+b)^3+(a+b)^2\log n\Big)\)。本方法可以通过。
Algorithm 2.二维卷积。
把 \((x+y)^a\) 展成 \(a!\sum\limits_{i=0}^a\dfrac{x^i}{i!}\times\dfrac{y^{a-i}}{(a-i)!}\)，然后设一个 \(f_{n,a,b}\) 表示此时的答案。合并 \(f_x\) 与 \(f_y\) 是二维卷积。但需要另外设一个态表示两端的 01 态。
用 FFT 的复杂度是 \((a+b)^2\log (a+b)\log n\)，但是常数大得要命。用三方卷积（自己瞎掰出的秦九韶+拉格朗日）常数依旧大得要命。总结起来就是过不去。
TLE 代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
ll n;
int a,b,fac[410],inv[410],lim;
void substi(int*f,int F){
static int g[410];
for(int i=0;i<=F;i++)for(int j=F;j>=0;j--)g[i]=(1ll*g[i]*i+f[j])%mod;
for(int i=0;i<=F;i++)f[i]=g[i],g[i]=0;
}
int coe[410],eoc[410];
void mul(int x,int F){
for(int i=F+1;i>=0;i--){coe[i]=1ll*coe[i]*x%mod;if(i)(coe[i]+=coe[i-1])%=mod;}
}
void del(int x,int F){
if(!x){for(int i=0;i<=F;i++)eoc[i]=coe[i+1];return;}
x=ksm(x);
for(int i=0;i<=F;i++){
eoc[i]=coe[i];
if(i)(eoc[i]+=mod-eoc[i-1])%=mod;
eoc[i]=1ll*eoc[i]*x%mod;
}
}
void interp(int*f,int F){
for(int i=0;i<=F+1;i++)coe[i]=0;
coe[0]=1;for(int i=0;i<=F;i++)mul(mod-i,F);
static int g[410];
for(int i=0;i<=F;i++){
del((mod-i)%mod,F);
int lam=1ll*f[i]*inv[i]%mod*((F-i)&1?mod-inv[F-i]:inv[F-i])%mod;
for(int j=0;j<=F;j++)g[j]=(1ll*eoc[j]*lam+g[j])%mod;
}
for(int i=0;i<=F;i++)f[i]=g[i],g[i]=0;
}
struct Poly{
int x[210][210];
Poly(){memset(x,0,sizeof(x));}
int*operator[](const int&i){return x[i];}
void print()const{
for(int i=0;i<=a;i++){putchar('[');for(int j=0;j<=b;j++)printf("%d%s",x[i][j],j==b?"]\n":" ");}
}
friend Poly operator*(Poly&u,Poly&v){
Poly w;
static int U[410][410],V[410][410];
memset(U,0,sizeof(U)),memset(V,0,sizeof(V));
for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)U[i][j]=u[i][j],V[i][j]=v[i][j];
for(int i=0;i<=a;i++)substi(U[i],b<<1),substi(V[i],b<<1);
for(int i=0;i<=a;i++)for(int j=i;j<=(b<<1);j++)swap(U[i][j],U[j][i]),swap(V[i][j],V[j][i]);
for(int i=0;i<=(b<<1);i++)substi(U[i],a<<1),substi(V[i],b<<1);
for(int i=0;i<=(b<<1);i++)for(int j=0;j<=(a<<1);j++)U[i][j]=1ll*U[i][j]*V[i][j]%mod;
for(int i=0;i<=(b<<1);i++)interp(U[i],a<<1);
for(int i=0;i<=(b<<1);i++)for(int j=i;j<=(a<<1);j++)swap(U[i][j],U[j][i]);
for(int i=0;i<=(a<<1);i++)interp(U[i],b<<1);
for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)w[i][j]=U[i][j];
// u.print(),puts("*"),v.print(),puts("="),w.print(),puts("");
return w;
}
friend Poly operator+(Poly u,Poly v){
Poly w;
for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)w[i][j]=(u[i][j]+v[i][j])%mod;
return w;
}
};
struct Tri{
Poly f[3];
Poly&operator[](const int&x){return f[x];}
friend Tri operator*(Tri&u,Tri&v){
Tri w;
w[0]=u[0]*v[0]+u[1]*v[0]+u[0]*v[1];
w[1]=u[0]*v[1]+u[1]*v[1]+u[0]*v[2];
w[2]=u[2]*v[1]+u[1]*v[2]+u[1]*v[1];
// for(int i=0;i<3;i++)u[i].print();puts("*");
// for(int i=0;i<3;i++)v[i].print();puts("=");
// for(int i=0;i<3;i++)w[i].print();puts("");
return w;
}
};
int calc(){
Tri z,x;bool upd=false;
for(int i=0;i<=a;i++)x[0][i][0]=inv[i];
for(int j=0;j<=b;j++)x[2][0][j]=inv[j];
for(;n;n>>=1,x=x*x)if(n&1){
if(upd)z=z*x;else z=x;
upd=true;
}
return(2ll*z[1][a][b]+z[0][a][b]+z[2][a][b])*fac[a]%mod*fac[b]%mod;
}
int main(){
freopen("fib.in","r",stdin);
freopen("fib.out","w",stdout);
scanf("%lld%d%d",&n,&a,&b),lim=max(a<<1,b<<1);
fac[0]=1;for(int i=1;i<=lim;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[lim]=ksm(fac[lim]);for(int i=lim;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
printf("%d\n",calc());
return 0;
}
Algorithm 3.斯特林+二项式
首先考虑将 \(x^ay^b\) 变成 \((n-y)^ay^b\)，然后二项式展成 \(\sum\limits_{i=0}^an^{a-i}(-1)^i\dbinom aiy^{b+i}\)。对于每个 \(i\in[a,a+b]\) 都求出对于所有排列的 \(y^i\) 之和，即可得到答案。
那么我们考虑对于某个特定的 \(b\) 计算 \(\sum y^b\)。套路之一是把它斯特林展开，即 \(y^b=\sum\limits_{i=0}^b\begin{Bmatrix}b\\i\end{Bmatrix}y^{\underline i}\)。按照套路，把下降幂展成二项式系数和阶乘，也即 \(y^b=\sum\limits_{i=0}^b\begin{Bmatrix}b\\i\end{Bmatrix}\dbinom yii!\)。这样，对于特定的 \(b\)，只要对于每个 \(i\) 求出 \(\sum\dbinom yi\) 即可。
那么随便设一个 \(f_{n,i}\) 表示长度为 \(n\) 的序列的 \(\dbinom yi\)。然后合并两个 \(f_n,f_m\) 时直接暴力背包并一下，最后设一个辅助维表示两端的状态即可。复杂度 \((a+b)^2\log n\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
ll n;
int a,b,fac[410],inv[410];
struct Poly{
int x[410];
Poly(){memset(x,0,sizeof(x));}
int&operator[](const int&i){return x[i];}
friend Poly operator*(Poly&u,Poly&v){
Poly w;
for(int i=0;i<=b;i++)for(int j=0;i+j<=b;j++)w[i+j]=(1ll*u[i]*v[j]+w[i+j])%mod;
return w;
}
friend Poly operator+(Poly u,Poly v){Poly w;for(int i=0;i<=b;i++)w[i]=(u[i]+v[i])%mod;return w;}
};
struct Tri{
Poly f[3];
Poly&operator[](const int&x){return f[x];}
friend Tri operator*(Tri&u,Tri&v){
Tri w;
w[0]=u[0]*v[0]+u[1]*v[0]+u[0]*v[1];
w[1]=u[0]*v[1]+u[1]*v[1]+u[0]*v[2];
w[2]=u[2]*v[1]+u[1]*v[2]+u[1]*v[1];
// for(int i=0;i<3;i++)u[i].print();puts("*");
// for(int i=0;i<3;i++)v[i].print();puts("=");
// for(int i=0;i<3;i++)w[i].print();puts("");
return w;
}
};
int f[410],g[410],S[410][410];
int calc(){
Tri z,x;bool upd=false;
x[0][0]=x[2][0]=x[2][1]=1;
for(ll y=n;y;y>>=1,x=x*x)if(y&1){if(upd)z=z*x;else z=x;upd=true;}
for(int i=0;i<=b;i++)f[i]=(2ll*z[1][i]+z[0][i]+z[2][i])*fac[i]%mod;
S[0][0]=1;
for(int i=1;i<=b;i++)for(int j=1;j<=i;j++)S[i][j]=(1ll*j*S[i-1][j]+S[i-1][j-1])%mod;
for(int i=0;i<=b;i++)for(int j=0;j<=i;j++)g[i]=(1ll*S[i][j]*f[j]+g[i])%mod;
int res=0;
for(int i=0;i<=a;i++){
int val=1ll*ksm(n%mod,a-i)*g[b-a+i]%mod*fac[a]%mod*inv[i]%mod*inv[a-i]%mod;
if(i&1)(res+=mod-val)%=mod;else(res+=val)%=mod;
}
return res;
}
int main(){
freopen("fib.in","r",stdin);
freopen("fib.out","w",stdout);
scanf("%lld%d%d",&n,&a,&b),b+=a;
fac[0]=1;for(int i=1;i<=b;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[b]=ksm(fac[b]);for(int i=b;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
printf("%d\n",calc());
return 0;
}
III.CF1097G Vladislav and a Great Legend
一种想法是用 \((x+y)^K=\sum\limits_{i=0}^Kx^iy^{K-i}\dbinom Ki\) 维护，然后记录 \(f\) 的 \(1\sim K\) 次幂。
但是这样合并就是 \(K^2\) 的，\(nK^2\) 无法通过。
那么我们尝试另一种思路。把它斯特林展开。
然后我们令一个 DP：\(f_{x,i}\) 表示所有以 \(x\) 节点为 LCA 的 \(\mathbb S\) 对应的 \(\dbinom{f(\bb S)}i\) 之和。
考虑合并两个态。有 \(\dbinom{x+y}z=\sum\limits_{i=0}^z\dbinom xi\dbinom y{z-i}\)。
转移可以直接用二项式系数的实际意义处理。因为 \(i\) 的下标上限即为 \(\max f(\bb S)\)，因此树上背包可以分析得复杂度是 \(O(nk)\) 的。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[100100][210],g[210],sz[100100],fac[210],res[210],S[210][210],ans;
vector<int>v[100100];
void dfs(int x,int fa){
f[x][0]=2;//choose or not.
for(auto y:v[x])if(y!=fa){
dfs(y,x),sz[y]=min(sz[y]+1,m);
for(int i=1;i<=sz[y];i++)g[i]=(f[y][i]+f[y][i-1])%mod;
for(int i=1;i<=sz[y];i++)f[y][i]=g[i],g[i]=0;
for(int i=0;i<=sz[x];i++)for(int j=0;j<=sz[y]&&i+j<=m;j++)
g[i+j]=(1ll*f[x][i]*f[y][j]+g[i+j])%mod;
sz[x]=min(sz[x]+sz[y],m);
for(int i=0;i<=sz[x];i++)(f[x][i]+=g[i])%=mod,g[i]=0;
}
(f[x][0]+=mod-1)%=mod;
for(int i=0;i<=sz[x];i++)(res[i]+=f[x][i])%=mod;
for(auto y:v[x])if(y!=fa)for(int i=0;i<=sz[y];i++)(res[i]+=mod-f[y][i])%=mod;//elimilate states from solely one son.
// printf("%d:\n",x);for(int i=0;i<=m;i++)printf("%d ",f[x][i]);puts("");
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
fac[0]=1;for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%mod;
S[0][0]=1;
for(int i=1;i<=m;i++)for(int j=1;j<=i;j++)S[i][j]=(1ll*j*S[i-1][j]+S[i-1][j-1])%mod;
dfs(1,0);
for(int i=0;i<=m;i++)ans=(1ll*S[m][i]*fac[i]%mod*res[i]+ans)%mod;
printf("%d\n",ans);
return 0;
}
V.笛卡尔树分治+线段树整体 DP
按照笛卡尔树分治是处理与区间最值有关的题目的手段之一。线段树则提供了维护 DP 数组以及更新的一种方式、
I.[IOI2018] meetings 会议
被人坑了说这题是CDQ分治的题，一小时想不出来开了题解发现是道DP
大概不会有人像我一样一开始想了极其诡异的DP，然后发现可以用莫队+树剖优化到 \(O(n\sqrt{n}\log^2n)\)，但是这复杂度估计比 \(n^2\) 还差……
扯远了，下面是正解。
一个主流的想法是设 \(f[i,j]\) 表示 \([i,j]\) 区间的答案，然后考虑转移。
考虑找到区间中的 \(\max\) 位置，不妨设为 \(k\)（如果有多个，随便取一个）。则，除非区间长为 \(1\)，否则在 \(k\) 这个位置集合一定不是最优解法，因为此时该区间中所有人的费用都是区间中最大值 \(a_k\)。集合位置要么是 \(k\) 左侧某个位置，然后右边的人走过来，代价全部为 \(k\)，要么相反。于是有
（当然，对于 \(i>j\) 的状态，要么直接不予考虑，要么设其为 \(0\)）
发现这两边形式一致，就可以只考虑一半东西，然后另一半直接将序列翻转再做一遍即可得到。但需要注意的是，两边转移的 \(k\) 值应该相同（这针对于有多个最大值的情形）。
我们不妨只考虑 \(f[k+1,j]+(k-i+1)a_k\) 这种转移。
因为转移多次涉及到区间 \(\max\)，所以有考虑笛卡尔树的可能。
然后发现，所有的 \(k\) 都是笛卡尔树上的一个节点，且 \(j\) 在其右侧子树中。
于是我们考虑求出从所有 \(k\) 开始，到其右侧子树中所有 \(j\) 的 \(f[k+1,j]\) 值。
因为我们明显不能显式地求出所有 \(f[k+1,j]\)（那样状态最劣仍是 \(O(n^2)\)），所以只能考虑借用旧的 \(f[k+1,j]\)。考虑用线段树维护。
然后我们发现，用线段树维护简直是一个天才般的想法，因为我们发现，\([k+1,j]\) 这一段，刚好是 \(k\) 右儿子的区间。
这就意味着 \(k\) 的DP值可以在右儿子的结果上稍加修改就得到。但这同样意味着，为了格式统一，\(k\) 要上传给它的父亲 \([i,j]\) 区间中，从 \(i\) 开始的所有值。
于是我们现在考虑求出如何求出 \([i,j]\)。
我们蓦然发现，实际上已经有了一半的值，因为 \([i,k-1]\) 就是左儿子上传上来的DP值。而 \([i,k]\) 又可以由 \([i,k-1]\) 简单得到（准确地说，加上一个 \(a_k\) 就行了）。
于是现在考虑应该如何在 \([k+1,j]\) 的基础上得到 \([i,j]\)。
祭出最上头的DP式，我们发现其有两种方式：一是左儿子中所有东西到右儿子去，右儿子中所有东西的DP值都要增加 \((k-l+1)a_k\)，显然很好在线段树上区间加维护；二是右儿子中所有东西到左儿子去，这时候，位置 \(j\) 就要变成 \(f[i,k]+(j-k)a_k\)，是等差数列的形式！
但是我们悲哀地发现，要执行的是区间与等差数列取 \(\min\)。这显然不是线段树能办到的事。
但是，转机来了：因为 \([k+1,j]\) 这段区间里所有元素都不大于 \(k\)，所以当从 \(f[k+1,j]\) 到 \(f[k+1,j+1]\) 时，二者间 \(\Delta\) 值是一定 \(\leq a_k\) 的！而上面的那个一次函数，相邻两个位置间的差是恒为 \(a_k\) 的。这就意味着，如果从某个位置开始区间加的结果首次比等差数列小了，则其右方的东西一定也小，左方的东西一定都大。
因此，采取等差数列的部分一定是从 \(k+1\) 开始的连续区间。直接在线段树上二分就行了。
时间复杂度 \(O(n\log n)\)。（但是常数极大）
需要多说一句的是，这里的笛卡尔树没必要显式地搞出来，只需要求出每个节点所对应的区间就行了，直接用ST表即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[750010],st[750010][20],LG[750010],ql[750010],qr[750010];
bool sec;//if we are executing the second round
ll res[750010];
int MAX(int x,int y){if(!sec)return a[x]>a[y]?x:y;else return a[x]>=a[y]?x:y;}
int RMQ(int x,int y){int k=LG[y-x+1];return MAX(st[x][k],st[y-(1<<k)+1][k]);}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define X x,l,r
#define LSON lson,l,mid
#define RSON rson,mid+1,r
struct SegTree{ll tagl,tagadd,lval,rval;int tagdelta;}seg[3001000];
void SETSEQ(int x,int l,int r,ll lval,int delta){seg[x].tagl=seg[x].lval=lval,seg[x].rval=lval+1ll*(r-l)*delta,seg[x].tagdelta=delta,seg[x].tagadd=0;}
void ADD(int x,ll val){if(seg[x].tagl!=-1)seg[x].tagl+=val;else seg[x].tagadd+=val;seg[x].lval+=val,seg[x].rval+=val;}
void pushup(int x){seg[x].lval=seg[lson].lval,seg[x].rval=seg[rson].rval;}
void pushdown(int x,int l,int r){
if(seg[x].tagl!=-1){
SETSEQ(LSON,seg[x].tagl,seg[x].tagdelta);
SETSEQ(RSON,seg[x].tagl+1ll*seg[x].tagdelta*(mid-l+1),seg[x].tagdelta);
seg[x].tagl=seg[x].tagdelta=-1;
}else ADD(lson,seg[x].tagadd),ADD(rson,seg[x].tagadd),seg[x].tagadd=0;
}
void modifysequence(int x,int l,int r,int L,int R,ll leftval,int delta){
if(l>R||r<L)return;
if(L<=l&&r<=R){SETSEQ(X,leftval+1ll*(l-L)*delta,delta);return;}
pushdown(X),modifysequence(LSON,L,R,leftval,delta),modifysequence(RSON,L,R,leftval,delta),pushup(x);
}
void modifyadd(int x,int l,int r,int L,int R,ll val){
if(l>R||r<L)return;
if(L<=l&&r<=R){ADD(x,val);return;}
pushdown(X),modifyadd(LSON,L,R,val),modifyadd(RSON,L,R,val),pushup(x);
}
ll query(int x,int l,int r,int P){
if(l==r)return seg[x].lval;
pushdown(X);
if(P<=mid)return query(LSON,P);else return query(RSON,P);
}
int innerbinaryonseg(int x,int l,int r,ll lval,int delta){
if(l==r)return l;
pushdown(X);
if(seg[rson].lval<=lval+1ll*(mid+1-l)*delta)return innerbinaryonseg(LSON,lval,delta);
else return innerbinaryonseg(RSON,lval+1ll*(mid+1-l)*delta,delta);
}
int outerbinaryonseg(int x,int l,int r,int L,int R,ll lval,int delta){
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
// printf("(%d,%d):%lld %lld\n",l,r,seg[x].lval,lval+1ll*(l-L)*delta);
// printf("(%d,%d):%lld %lld\n",l,r,seg[x].rval,lval+1ll*(r-L)*delta);
if(seg[x].rval>lval+1ll*(r-L)*delta)return -1;
if(seg[x].lval<=lval+1ll*(l-L)*delta)return l-1;
return innerbinaryonseg(X,lval+1ll*(l-L)*delta,delta);
}
pushdown(X);
int tmp=outerbinaryonseg(LSON,L,R,lval,delta);if(tmp!=-1)return tmp;
return outerbinaryonseg(RSON,L,R,lval,delta);
}
vector<int>v[750010];
void iterate(int x,int l,int r){
if(l==r){printf("%lld ",seg[x].lval);return;}
pushdown(X),iterate(LSON),iterate(RSON);
}
void solve(int l,int r){
if(l==r){modifysequence(1,1,n,l,r,a[l],0);return;}
int o=RMQ(l,r);
if(l!=o)solve(l,o-1);
if(r!=o)solve(o+1,r);
// printf("[%d,%d]:%d\n",l,r,o);
for(auto i:v[o])res[i]=min(res[i],query(1,1,n,qr[i])+1ll*(o-ql[i]+1)*a[o])/*,printf("QQ:%d\n",query(1,1,n,qr[i])+1ll*(o-ql[i]+1)*a[o])*/;
ll FO;modifysequence(1,1,n,o,o,FO=(l==o?a[o]:query(1,1,n,o-1)+a[o]),0);
if(r!=o)modifyadd(1,1,n,o+1,r,1ll*(o-l+1)*a[o]);
// iterate(1,1,n),puts("");
if(r!=o){
int P=outerbinaryonseg(1,1,n,o+1,r,FO+a[o],a[o]);if(P==-1)P=r;//printf("%d\n",P);
if(P>=o+1)modifysequence(1,1,n,o+1,P,FO+a[o],a[o]);
}
// iterate(1,1,n),puts("");
}
void calc(){
for(int i=1;i<=n;i++)st[i][0]=i,v[i].clear();
for(int j=1;j<=LG[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=MAX(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++){int o=RMQ(ql[i],qr[i]);if(o!=qr[i])v[o].push_back(i);}
// for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
solve(1,n);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)LG[i]=LG[i>>1]+1;
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&ql[i],&qr[i]),ql[i]++,qr[i]++;
if(ql[i]!=qr[i])res[i]=0x3f3f3f3f3f3f3f3f;else res[i]=a[ql[i]];
}
calc();
sec=true,reverse(a+1,a+n+1);for(int i=1;i<=m;i++)ql[i]=n-ql[i]+1,qr[i]=n-qr[i]+1,swap(ql[i],qr[i]);calc();
for(int i=1;i<=m;i++)printf("%lld\n",res[i]);
return 0;
}
II.[PA2014]Druzyny
一个平方的 DP 首先是简单且平凡的——设 \(f_i\) 表示长度为 \(i\) 的前缀的 DP 值然后暴力转移即可。
考虑优化。首先假设仅有 \(c\) 的限制。此时建立笛卡尔树，则我们知道了每个区间转移时所需最短长度。
考虑在笛卡尔树上用 CDQ 分治的形式进行更新。于是我们现在要用 \([l,m]\) 去更新 \([m,r]\)。
考虑枚举 \(i\in[m,r]\)，则因为我们忽略了 \(d\) 的限制，所以区间 \([l,i-c_m]\) 中所有元素都能更新到 \(i\)。随着 \(i\) 每次右移一步，该区间右边界也右移一位。递增枚举 \(i\)，直到 \(i\) 增加到 \(r\) 或 \(i-c_m\) 增加到 \(m\) 二者中某者发生、
假如是前者，复杂度是 \(O(r-m)\)；假如是后者，我们已经进行的复杂度是 \(O(m-l)\)，且剩下的 \([i,r]\) 区间中所有元素能被更新的区间都是 \([l,m]\) 全体。用一个线段树区间更新即可。
现在考虑分析复杂度。复杂度分为三部分：分治的复杂度、枚举 \(i\) 的复杂度、线段树的复杂度。分治会恰好进行 \(n\) 次；枚举 \(i\) 的复杂度是 \(\min\Big((r-m),(m-l)\Big)\)。这个复杂度可能不是很好分析，但是注意到你把分治树逆过来，这个复杂度就是启发式合并的复杂度，故其事实上复杂度就和启发式合并一样是 \(O(n\log n)\)（其被称作启发式分裂）。线段树总共会更新 \(n\) 次，复杂度也是 \(n\log n\)。总复杂度 \(n\log n\)。
现在考虑 \(d\) 的限制。我们可以求出 \(lim_i\) 表示以 \(i\) 为右端点时，仅考虑 \(d\) 的限制时左端点可能的最小值。可以发现 \(lim\) 是递增的。
考虑处理 \(lim\) 对转移的影响。其影响就在于更新的区间可能不是 \([l,i-c_x]\) 而是 \([lim_i,i-c_x]\)。
考虑所有能够更新到 \(i\) 的 \([l,r]\) 区间，会发现它们两两无交。这意味着，只会有一个 \([l,r]\) 恰好横跨 \(lim_i\)。于是，我们可以维护一个 \(j\) 表示当前转移区间的左边界。如果发现 \(lim_i>j\)，则把 \(j\) 设成 \(lim\) 并且在线段树上查询得到此时的区间结果。这只会在横跨的时刻被执行，而横跨的时刻仅有 \(n\) 个，故其复杂度为 \(n\log n\)。总复杂度为 \(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;
struct dat{
int mx,way;
dat(){mx=way=0;}
dat(int M,int W){mx=M,way=W;}
friend dat operator+(const dat&u,const dat&v){
dat w;w.mx=max(u.mx,v.mx);
if(w.mx==u.mx)w.way+=u.way;
if(w.mx==v.mx)w.way+=v.way;
w.way%=mod;
return w;
}
};
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{dat mx,tag;void ADD(dat y){mx=mx+y,tag=tag+y;}}seg[4001000];
void pushup(int x){seg[x].mx=seg[lson].mx+seg[rson].mx;}
void pushdown(int x){seg[lson].ADD(seg[x].tag),seg[rson].ADD(seg[x].tag),seg[x].tag=dat();}
void modify(int x,int l,int r,int L,int R,dat val){
if(l>R||r<L)return;
if(L<=l&&r<=R)return seg[x].ADD(val);
pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);
}
dat query(int x,int l,int r,int L,int R){
if(l>R||r<L)return dat();
if(L<=l&&r<=R)return seg[x].mx;
pushdown(x);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
int L[1001000],R[1001000],lim[1001000],stk[1001000],tp,ch[1001000][2];
dat f[1001000];
void solve(int x,int l,int r){
if(!x)return;
// printf("SOLVE:%d[%d,%d]\n",x,l,r);
solve(ch[x][0],l,x-1);
int i=max(l+L[x]-1,x),j=l;
dat val=query(1,0,n,j-1,i-L[x]-1);
for(;i<=r;i++){
if(i-L[x]+1>x)break;
if(i-L[x]+1>=j)val=val+f[i-L[x]];
if(lim[i]>j)j=lim[i],val=query(1,0,n,j-1,i-L[x]);
// printf("|%d:%d,%d|:%d,%d\n",i,j,i-L[x]+1,val.mx,val.way);
f[i]=f[i]+val;
}
while(i<=r){
int k=upper_bound(lim+i,lim+r+1,j)-lim;
// printf("<%d,%d>:%d,%d\n",i,k,val.mx,val.way);
modify(1,0,n,i,k-1,val);
j=lim[k],val=query(1,0,n,j-1,x);
i=k;
}
f[x]=f[x]+query(1,0,n,x,x);
f[x].mx++;if(!f[x].way)f[x].mx=0;modify(1,0,n,x,x,f[x]);
// printf("[%d:%d,%d]\n",x,f[x].mx,f[x].way);
solve(ch[x][1],x+1,r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&L[i],&R[i]);
lim[0]=1;
for(int i=1,pt=1;i<=n;i++){
while(tp&&R[stk[tp]]>=R[i])tp--;
stk[++tp]=i,pt=min(pt,tp),lim[i]=lim[i-1];
while(true){
// printf("%d,%d,%d,%d\n",i,lim[i],pt,stk[pt]);
while(lim[i]>stk[pt])pt++;
if(R[stk[pt]]>=i-lim[i]+1)break;
lim[i]++;
}
}
// for(int i=1;i<=n;i++)printf("%d ",lim[i]);puts("");
tp=0;
for(int i=1;i<=n;i++){
while(tp&&L[stk[tp]]<=L[i])ch[i][0]=stk[tp--];
if(tp)ch[stk[tp]][1]=i;stk[++tp]=i;
}
modify(1,0,n,0,0,f[0]=dat(0,1));
solve(stk[1],1,n);
if(!f[n].way)puts("NIE");else printf("%d %d\n",f[n].mx,f[n].way);
return 0;
}
VI.DP 函数化
有时对于一个二维 DP，可以把它写成以一维为参数的函数 \(f_i(x)\)。除了用数据结构维护外，观察该函数本身性质亦可解决问题。
I.Y星人
题意：给定一张 \(n\times m\) 的网格。在 \(q\) 次询问中，你每次要从位置 \((1,1)\) 走到给定的位置 \((x,y)\)。
从位置 \((x,y)\) 令 \(x\) 加一的代价是 \(c_y\)，令 \(y\) 加一的代价则是 \(x^2\)。求最小代价。
数据范围：\(1\leq x\leq n\leq10^9,1\leq y\leq m\leq2\times10^5,0\leq c_y\leq10^9\)。
设到位置 \((i,x)\) 的代价为 \(f_i(x)\)。考虑 \(f_{i-1}\to f_i\)。
其变化即为 \(f(x)\) 增加 \(x^2\)，然后 \(f(x)\) 与 \(f(x-1)+c_y\) 取 \(\min\)。
显然 \(f(x)\) 是增函数。不仅如此，归纳证明可得其是凹函数，也即其导数不降、二阶导非负。取 \(\min\) 的操作就是把函数最后一些差分过大的位置的差分赋作 \(c_y\) 的操作。
用栈维护当前的函数。每次删掉栈尾那些过大的差分，并放入一个差分为 \(c_y\) 的函数。增加 \(x^2\) 的操作可以打时间戳表示上次被取 \(\min\) 的时刻来解决。询问就直接二分得到栈中的坐标即可。复杂度对数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,a[200100],tp,tim[200100],slp[200100];
ll res[200100],val[200100],pos[200100];
namespace FIFO{
char buf[1<<23],*p1=buf,*p2=buf;
#ifndef Troverld
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#else
#define gc() getchar()
#endif
template<typename T>void read(T&x){
x=0;
char c=gc();
while(c>'9'||c<'0')c=gc();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc();
}
template<typename T>void print(T x){if(x<=9)putchar('0'+x);else print(x/10),putchar('0'+x%10);}
}using namespace FIFO;
vector<pair<int,int> >v[200100];
int main(){
freopen("ylien.in","r",stdin);
freopen("ylien.out","w",stdout);
read(n),read(m);
for(int i=1;i<=m;i++)read(a[i]);
read(q);
for(int i=1,x,y;i<=q;i++)read(x),read(y),v[y].emplace_back(x,i);
tp=1,tim[1]=pos[1]=1,val[1]=0,slp[1]=a[1];
for(auto x:v[1])res[x.second]=1ll*a[1]*(x.first-1);
for(int i=2;i<=m;i++){
while(tp>=2){
ll x=1ll*(i-tim[tp-1])*(pos[tp]-1)*(pos[tp]-1)+
slp[tp-1]*(pos[tp]-1-pos[tp-1])+val[tp-1];
ll y=1ll*(i-tim[tp])*pos[tp]*pos[tp]+val[tp];
if(x+a[i]>y)break;
tp--;
}
int l=pos[tp],r=n+1;
while(l<r){
int mid=(l+r)>>1;
ll x=1ll*(i-tim[tp])*mid*mid+slp[tp]*(mid-pos[tp]);
ll y=1ll*(i-tim[tp])*(mid+1)*(mid+1)+slp[tp]*(mid+1-pos[tp]);
if(x+a[i]>y)l=mid+1;else r=mid;
}
if(l<=n){
pos[tp+1]=l,val[tp+1]=1ll*(i-tim[tp])*l*l+slp[tp]*(l-pos[tp])+val[tp];
slp[tp+1]=a[i],tim[tp+1]=i;
if(pos[tp+1]==pos[tp])val[tp]=val[tp+1],slp[tp]=slp[tp+1],tim[tp]=tim[tp+1];
else tp++;
}
for(auto x:v[i]){
int t=upper_bound(pos+1,pos+tp+1,x.first)-pos-1;
res[x.second]=1ll*(i-tim[t])*x.first*x.first+slp[t]*(x.first-pos[t])+val[t];
}
}
for(int i=1;i<=q;i++)print(res[i]),putchar('\n');
return 0;
}
II.SolarPea 与网格
给定一列 \(n\) 个格子，第 \(i<n\) 个格子上的权值是 \(a_i\)，有 \(q\) 次询问，每次询问给出第 \(n\) 个格子的权值。
初始时，A 的棋子位于第一个格子，B 的棋子位于第二个格子。重复执行如下操作：
- 两个人中棋子较靠前的一个，将其棋子向前移动，但是不能与另一个人的棋子重合，也不能不移动。
一个人的权值为其经过所有格子的权值之和。两个人都希望最大化其与另一个人的权值差。对每次询问，求最终权值。
数据范围：\(n,q\leq2\times10^5,\sum\limits_{i=1}^{n-1}a\leq10^6,a_n\leq10^9\)。所有 \(a\) 均为非负整数。
首先先假定 \(n\) 的权值已被确定。那么显然可以令一个 DP：令 \(f_i\) 为两枚棋子中较靠后的一个位于 \(i\)，且较靠前的那个位于 \(i+1\) 时，位于 \(i\) 的人的权值减去 \(i+1\) 的人的权值的结果。（\(i\) 和 \(i+1\) 的权值均不计入）
于是有 \(f_{n-2}=a_n\)，\(f_i=\max\limits_{j=i+2}^n\{a_j-f_{j-1}-(s_{j-1}-s_{i+1})\}\)。
然后我们发现 \(f_i\) 的转移式和 \(f_{i+1}\) 的转移式看上去很像。事实上，直接有 \(f_i=\max(f_{i+1}-s_{i+2}+s_{i+1},a_{i+1}-f_{i+2}-(s_{i+1}-s_{i+1}))=\max(f_{i+1}-a_{i+2},a_{i+2}-f_{i+1})=|f_{i+1}-a_{i+2}|\)。
这个式子是很好的。我们考虑增量构造。记 \(g_i(x)\) 为 \(f_i=x\) 时，\(f_1\) 的最终值。则 \(i\) 增加 \(1\) 后，流程是：
- 将 \(f\) 向右平移 \(a_i\) 后关于 \(a_i\) 对称。
直接每次暴力修改前 \(a_i\) 项即可。用一个 vector 维护即可。
时间复杂度线性。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,q,a[200100],f[200100];
vector<int>v;
const int N=2e6;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<=N;i++)v.push_back(i);
reverse(v.begin(),v.end());
for(int i=3;i<n;i++){
int p=v.size()-1;
for(int j=1;j<=a[i];j++)v.push_back(v[p-j]);
}
reverse(v.begin(),v.end());
scanf("%d",&q);
for(int i=1,x;i<=q;i++){
scanf("%d",&x);
int val;
if(x<v.size())val=v[x];
else val=v.back()+(x-v.size()+1);
val+=a[1]-a[2];
printf("%d\n",val);
}
return 0;
}
VII.换根 DP 转记忆化搜索的 trick
换根 DP 是很麻烦的 DP 类型之一。无论是记录前后缀和还是求逆元还是用 set 之类大力维护，都十分恶心。
一个初学者很容易想到的方法是，对于每条边的两个方向分别设一个 DP 态。
但是这样的复杂度事实上是 \(O(\sum d^2)\) 的。在菊花图时会被卡到平方。
怎么办呢？我们注意到在一类 与边关联较大 的 DP 时，我们可以把一个有 \(d\) 个儿子的节点拆成一个儿子和一个有 \(d-1\) 个儿子的节点，并与后者连一条长度为 \(0\) 的边。
听说这也是边分治的 trick 之一。
I.分身游走
题意：给定一棵 \(n\) 个点的带权树。对于每个点，求出有 \(m\) 个人从之出发，遍历整棵树（并不一定需要回到起点）所需要移动的最小总路程。
数据范围：\(n\leq15000,m\leq30\)。边权 \(\leq100\)。
首先一个显然的想法是换根 DP。怎么设计状态呢？令 \(f_{i,j,k}\) 表示节点 \(i\)，来了 \(j\) 个人，并有 \(k\) 个人活着回去的最小代价。
但是这个做法有一个重大的缺点：就是你不知道应该按照什么顺序遍历这些节点，并在什么地方最终停下。
虽然我也有一个从浅儿子向深儿子依次处理的 observation，但是事实上这不好。
Observation 1.到达一个点的所有人，要么全都活着回去，要么全都不回去。
假如有人活着回去，有人没有，那把活着回去人的任务全都交给死了的那个人，然后活着回去的人自始至终都不用下来，直接在父亲处待命即可。
于是我们简单设一个 \(f_{i,j}\) 表示节点 \(i\) 来了 \(j\) 个人，然后转移就可以简单处理了。
Observation 2.假如有超过两个人到达一个点，那么它们没有一个能够活着回去。
依据 Observation 1，这些人要么全活着回去，要么全死了。全活着回去的情形不如把工作全推给同一个人然后只派一个人下来，故能活着回来的只有一个人。
考虑那些“遍历众多节点后死在某个点的人”，它们遍历的顺序是有关的；但是，注意到必然有至少一个人被派下来了，则这个人可以手动把流程调整为“先遍历能活着回来的儿子，最后遍历葬身的儿子”，故我们事实上可以认为，不管还剩几个人，总是能派一个人遍历整棵子树。
于是我们把状态分为两个：\(f_{i,j}\) 表示派 \(j\) 个人下来 送死 的最小路程，以及 \(f_{i,0}\) 表示送一个人下来“旅游”的最小路程。这样就可以简单转移了。转移是简单背包。
这道题因为我们并不在意边权，所以可以直接应用上述 trick，就不用换根 DP 了。虽然，本题就算要换根 DP 也很简单就是了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
void chmn(int&x,int y){if(x>y)x=y;}
struct DP{
int a[32];
DP(){memset(a,0,sizeof(a));}
friend void operator+=(DP&u,const DP&v){
static int w[32];memset(w,0x3f,sizeof(w));
for(int i=0;i<=m;i++)for(int j=0;i+j<=m;j++)chmn(w[i+j],u.a[i]+v.a[j]);
for(int i=0;i<=m;i++)u.a[i]=w[i];
}
friend DP operator+(const DP&u,const DP&v){
DP w;for(int i=0;i<=m;i++)w.a[i]=0x3f3f3f3f;
for(int i=0;i<=m;i++)for(int j=0;i+j<=m;j++)chmn(w.a[i+j],u.a[i]+v.a[j]);
return w;
}
friend DP operator+(const DP&u,const int&v){
DP w=u;
for(int i=1;i<=m;i++)w.a[i]+=v*i;
for(int i=2;i<=m;i++)chmn(w.a[i],w.a[i-1]);
w.a[0]+=2*v;
return w;
}
int operator~()const{int ret=0x3f3f3f3f;for(int i=0;i<=m;i++)ret=min(ret,a[i]);return ret;}
void operator!()const{for(int i=0;i<=m;i++)printf("%d ",a[i]);puts("");}
}f[15100],g[15100],pre[15100],suf[15100];
vector<pair<int,int> >v[15100];
void dfs1(int x,int fa){
for(auto i:v[x]){
int y=i.first,z=i.second;
if(y==fa)continue;
dfs1(y,x),f[x]+=f[y]+z;
}
}
void dfs2(int x,int fa){
if(fa)swap(f[fa],g[x]);
pre[v[x][0].first]=DP();for(int i=0;i+1<(int)v[x].size();i++)
pre[v[x][i+1].first]=pre[v[x][i].first]+(f[v[x][i].first]+v[x][i].second);
suf[v[x].back().first]=DP();for(int i=(int)v[x].size()-1;i>=1;i--)
suf[v[x][i-1].first]=(f[v[x][i].first]+v[x][i].second)+suf[v[x][i].first];
if(fa)swap(f[fa],g[x]);
for(auto i:v[x]){
int y=i.first,z=i.second;
if(y==fa)continue;
g[y]=pre[y]+suf[y];
f[y]+=g[y]+z;
dfs2(y,x);
}
}
int main(){
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<n;i++)
scanf("%d%d%d",&x,&y,&z),v[x].emplace_back(y,z),v[y].emplace_back(x,z);
dfs1(1,0),dfs2(1,0);
for(int i=1;i<=n;i++)printf("%d\n",~f[i]);
return 0;
}
VIII.值域优化 DP
从值域方面下手去优化 DP 是常见的优化套路之一。当值域相对于定义域较小时可以尝试把值域引入状态以减小状态数。
但是我们不仅仅要关注值域本身，还可以关注值域的 差分 或者 不同值的个数 之类。比如说，对于一些问题，DP 数组差分会得到 01 序列，进而可以 bitset 优化；对于令一些问题，分析得到只有根号以内的值是有用的，等等。
I.[LOJ#6564]最长公共子序列
\(f_{i,j}\) 表示 A 串长为 \(i\) 的前缀与 B 串长为 \(j\) 的前缀的 LCS，然后暴力转移，这可以写出平方的暴力。
依据转移式，我们令 \(d_i(j)=f_{i,j}-f_{i,j-1}\)。可以发现，\(d_i\) 所有位的取值都是 01。
那么用 bitset 大力维护 \(d\) 的变化即可。复杂度 \(\dfrac{n^2}\omega\)。
具体而言，考虑 \(d\) 的构成：若干段 \(1\) 开始，后跟若干个 \(0\) 的东西。
从 \(d_i\) 到 \(d_{i+1}\)，我们首先完全继承，然后考虑所有与 \(A_{i+1}\) 相同的 B 中元素的下标构成的 bitset，记作 \(o\)。
其操作可描述为：把该 \(o\) 中每个 1 的下一个 1 赋成 0，然后把所有 1 的位置赋成 1。
但是这个做法必须按照从高位往低位的顺序处理，有后效性。
上述想法是把 1000... 作为单位来搞，我们这回用 ...001 作为单位。若一段这样的段中存在一个 \(o\) 中的 1 位，那就把这个 1 移到出现的首个 1 的位置（最后一段的 000 另说）。为了统一不出现 1 和出现 1 的情形，我们把 \(o\) 与 \(d\) 做或即可。
如何找到每一段中的第一个 1 的位置呢？使用 lowbit 算法，我们得知其可以被 \(((x-1)\operatorname{xor}x)\operatorname{and}x\) 来描述。
两个 bitset 的减法可以通过手动用若干 unsigned long long 模拟实现；故现在我们只需对于每一段，往其最低位插一个 1 即可。这可以通过全体左移一位并在开头插 1 实现。
那么我们计算 \(x-1\)，然后异或上 \(x\)，然后在与上 \(x\)，即可。
复杂度 \(\dfrac{nm}\omega\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,m;
const int B=1100;
struct Bitset{
ull a[B];
friend Bitset operator^(const Bitset&u,const Bitset&v){Bitset w;for(int i=0;i<B;i++)w.a[i]=u.a[i]^v.a[i];return w;}
friend Bitset operator|(const Bitset&u,const Bitset&v){Bitset w;for(int i=0;i<B;i++)w.a[i]=u.a[i]|v.a[i];return w;}
friend Bitset operator&(const Bitset&u,const Bitset&v){Bitset w;for(int i=0;i<B;i++)w.a[i]=u.a[i]&v.a[i];return w;}
friend Bitset operator-(const Bitset&u,const Bitset&v){
Bitset w;
for(int i=0,car=0;i<B;i++)if(car){
if(!u.a[i]){w.a[i]=-1-v.a[i],car=1;continue;}
w.a[i]=u.a[i]-1;
car=(w.a[i]<v.a[i]);
w.a[i]-=v.a[i];
}else car=(u.a[i]<v.a[i]),w.a[i]=u.a[i]-v.a[i];
return w;
}
void leftshift(){a[B-1]<<=1;for(int i=B-1;i;i--)a[i]|=(a[i-1]>>63),a[i-1]<<=1;}
void set(int x){a[x>>6]|=(1ull<<(x&63));}
bool test(int x)const{return (a[x>>6]>>(x&63))&1;}
void print()const{for(int i=0;i<=m;i++)printf("%d",test(i));puts("");}
}f,o[70100];
int a[70100],b[70100];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]),o[b[i]].set(i);
for(int i=1;i<=n;i++){
Bitset g=f|o[a[i]];
Bitset h=f;h.leftshift(),h.set(0);
// printf("G");g.print();
// printf("H");h.print();
h=g-h;//printf("G-H");h.print();
h=h^g;//printf("G^H");h.print();
h=h&g;//printf("G&H");h.print();
f=h;
// o[a[i]].print();
// f.print();
}
int res=0;
for(int i=1;i<=m;i++)res+=f.test(i);
printf("%d\n",res);
return 0;
}
IX.特殊的断环成链
“将环断成若干段，使得每段上的函数的合并结果取到最值”，这个问题是很常见的。在 \(n\) 小时，一个可行的想法是随便挑一个位置然后用区间 DP 处理。在函数可以用简单的数学语言描述时，也可以尝试对跨分界点的区间的左右端点讨论。
但是如果上述两条件均不满足，又应该怎么办呢？
这时，常常会存在某个位置，其必然会被切一刀；或者，包含该位置的函数可以用简单数学语言描述。挑选这样的位置切割，可以让分析简便。
I.foo~
在一个圆排列上切恰 \(k\) 刀，得到若干段区间。每段区间的权值是 \(\max(\text{前缀最大值个数},\text{后缀最大值个数})\)。最大化权值和。
数据范围：\(k\leq n\leq6\times10^5,k\leq30\)。
什么位置最特殊呢？显然是 \(n\)。\(n\) 左侧的东西都只能以前缀最大值贡献，而右侧的东西都只能以后缀最大值贡献。
但是并非必然会在 \(n\) 旁切刀：例如 45321 这个排列，切一刀的最优方式就是在 14 中间切一刀，结果就是 45321。
还有什么解决方法呢？事实上，因为是 \(\max(\text{前缀最大值个数},\text{后缀最大值个数})\)，则我们可以将 \(n\) 提前到序列首，然后钦定 \(n\) 所在的区间以后缀最大值贡献入答案。这样，\(n\) 所在段的前一半就表现为整个序列的一段后缀，而这段后缀是没有贡献的。于是我们直接将序列正反各处理一次，然后答案即为处理的时候所有前缀方案的最大值。
断环成链成功后，剩下的就是 DP 了。\(k\) 很小启发我们关于 \(k\) 分层 DP。记 \(f_i\) 表示长度为 \(i\) 的前缀的答案，\(g_i\) 表示前一次划分时长度为 \(i\) 的前缀的答案。
转移仍然要把前缀最大值和后缀最大值拆开。首先先思考前缀最大值：将每个 \(a_i\) 向其后方首个比它大的元素连边，则区间 \([i,j]\) 中前缀最大值数量，即为 \(i\) 的所有祖先中下标小于等于 \(j\) 的元素数。
考虑 \(i\) 的所有祖先 \([x_0=i,x_1,x_2,x_3,\dots,x_k,x_{k+1}=n+1]\)。我们可以求出所有的 \([x_i,x_{i+1})\) 这段中的贡献。对于所有的 \([i,fa_i)\)，我们都可以求出其中最大贡献。于是现在有一个这样的问题：
- 给定若干 \([l,r]\)，将其中所有元素与 \(x\) 取 \(\max\)。求最终结果。
对数数据结构随便搞。桶排后冰茶姬也是可行的。
后缀最大值直接单调栈爆算即可。这部分复杂度可以轻松线性。
总复杂度线性阿克曼。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[600100],n,m;
int f[600100],g[600100],res,stk[600100],tp,nex[600100];
int mx[600100],vl[600100];
int h[600100];
int dsu[600100];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
vector<int>v[600100];
void amin(){
memset(f,0xc0,sizeof(f));
mx[0]=0xc0c0c0c0;for(int i=1;i<=n;i++){
int MX=g[i-1];
while(tp&&a[stk[tp]]<a[i])MX=max(MX,vl[tp--]);
stk[++tp]=i,vl[tp]=MX,mx[tp]=max(mx[tp-1],MX-tp);
f[i]=max(f[i],mx[tp]+tp+1);
}tp=0;
memset(h,0xc0,sizeof(h));
for(int i=1;i<=n;i++){
h[i]=max(h[i],g[i-1]+1);
h[nex[i]]=max(h[nex[i]],h[i]+1);
}
for(int i=1;i<=n+1;i++)dsu[i]=i;
for(int i=1;i<=n;i++)if(h[i]>0)v[h[i]].push_back(i);
for(int i=n;i;i--)for(auto j:v[i]){
for(int k=find(j);k<nex[j];k=find(k))
f[k]=max(f[k],i),dsu[k]=k+1;
v[i].clear();
}
}
void mina(){
stk[0]=n+1;for(int i=n;i;i--){
while(tp&&a[stk[tp]]<a[i])tp--;
nex[i]=stk[tp],stk[++tp]=i;
}tp=0;
memset(f,0xc0,sizeof(f)),f[0]=0;
for(int i=1;i<=m;i++)swap(f,g),amin();
for(int i=1;i<=n;i++)res=max(res,f[i]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
rotate(a+1,find(a+1,a+n+1,n),a+n+1);
mina();
reverse(a+2,a+n+1);
mina();
printf("%d\n",res);
return 0;
}
X.数据处理获得单调性
有时候，初始的数据并不存在单调性；但是通过一些简单的处理手段（贪心之类），我们可以找到单调性。
I.分组
题意：将一个数列 \(a\) 分成不超过 \(m\) 段。一段数的 单位费用 为其中的 \(\max\)，代价 为其长度乘以 这段以及之前所有段的单位费用的和。
求最小总代价。
数据范围：\(1\leq m\leq n\leq5\times10^5,1\leq a_i\leq10^9\)。
首先一眼看出这个东西关于 \(m\) 是凸的。那就套一个 wqs 二分在外面罢。
然后考虑区间费用。简单推理后得到 \(\omega(l,r)=(n-l+1)\max\limits_{i\in[l,r]}\{a_i\}\)。
很遗憾，这个东西 不满足四边形不等式。那应该怎么优化呢？
注意到若对于 \(i<j\) 有 \(a_i\geq a_j\)，且 \(i,j\) 不被划在同一段中，且 \(a_i\) 是其所在段的 \(\max\)。
则，\(a_i\) 无论与不与 \(a_j\) 分在一组，其都会对 \(a_j\) 有贡献——这是由定义式决定的。
故，我们发现原始的 \(a_i\) 与 取前缀 \(\max\) 后 的 \(a_i\) 答案相同。
取前缀 \(\max\) 后，代价就满足四边形不等式了。观察发现可以简单斜率优化。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,a[500100],stk[500100],rt,tp,ch[500100][2];
struct dat{
ii a;int b;
dat(){a=1e25,b=0;}
dat(ii A,int B){a=A,b=B;}
dat operator+(const ll&v)const{return dat(a+v,b);}
friend bool operator<=(const dat&u,const dat&v){return u.a==v.a?u.b<=v.b:u.a<=v.a;}
}f[500100];
ll bon;
int q[500100],l,r;
bool DP(){
f[1]=dat(0,0);
l=1,r=0;
for(int i=2;i<=n+1;i++){
while(l<r){
ii u=(f[q[r-1]].a-f[q[r]].a)*(q[r]-i+1),v=(f[q[r]].a-f[i-1].a)*(q[r-1]-q[r]);
if(u>v||u==v&&f[q[r]].b>=f[i-1].b)r--;
else break;
}
q[++r]=i-1;
while(l<r&&f[q[l+1]]+1ll*(n-q[l+1]+1)*a[i-1]<=f[q[l]]+1ll*(n-q[l]+1)*a[i-1])l++;
f[i]=f[q[l]]+1ll*(n-q[l]+1)*a[i-1]+bon,f[i].b++;
}
return f[n+1].b<=m;
}
int main(){
freopen("group.in","r",stdin);
freopen("group.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]=max(a[i],a[i-1]);
ll l=0,r=5e14;
while(l<r){bon=(l+r)>>1;if(DP())r=bon;else l=bon+1;}
bon=l,DP();
printf("%lld\n",(ll)(f[n+1].a-(ii)min(f[n+1].b,m)*l));
return 0;
}
II.武装直升机
将整数序列分段，每段长度不小于 \(m\)。最小化每段中元素极差的最大值。
对序列的所有前缀求出此值，或 \(0\) 当其无解。强制在线。
数据范围：\(n\leq5\times10^6\)。
DP。令 \(f_i\) 为 \(i\) 的前缀的答案。
于是 \(f_i=\min\limits_{j=1}^{i-m+1}\Bigg\{\max\Big(f_{j-1},\max\limits_{k\in[j,i]}a_k-\min\limits_{k\in[j,i]}a_k\Big)\Bigg\}\)。
但是我们似乎不太好分析：因为 \(f\) 不具有单调性……吗？
不需要！
因为极差具有单调性，所以其实只要选取所有后缀 \(\min\) 的 \(f\) 即可。
那么我们用一个单调栈维护 \(f\) 的后缀 \(\min\)：在一段前缀中，极差占上风；在一段后缀中，\(f\) 占上风。随着 \(i\) 的不断增大，极差占上风的段会不断延长（因为，新来的 \(f\) 不可能大于该极差），于是我们只需用一个变量维护极差段的值，然后将其与后缀 \(f\) 的 \(\min\) 取 \(\min\) 转移即可。
首个 \(f\) 占上风的位置易维护；最后一个极差占上风的位置较难维护，不过注意到我们其实并不在意：如果该位置并非 \(f\) 的后缀最小值位置，则显然定不优，于是只要找到所有后缀最小值位置中，首个 \(f\) 占上风位置的前一个即可。
复杂度线性。
代码：
const int N=5001000;
int n,m;
int a[N],res[N],f[N];
int qmn[N],mnl,mnr;
int qmx[N],mxl,mxr;
int QMN[N],MNL,MNR;
int QMX[N],MXL,MXR;
int qf[N],fl,fr;
int main(){
freopen("group.in","r",stdin);
freopen("group.out","w",stdout);
read(n),read(m);
for(int i=1,P=0;i<=n;i++){
// printf("[%d]\n",i);
read(a[i]),a[i]^=f[i-1];
while(mnl!=mnr&&a[qmn[mnr-1]]>=a[i])mnr--;qmn[mnr++]=i;
while(mxl!=mxr&&a[qmx[mxr-1]]<=a[i])mxr--;qmx[mxr++]=i;
while(MNL!=MNR&&a[QMN[MNR-1]]>=a[i])MNR--;QMN[MNR++]=i;
while(MXL!=MXR&&a[QMX[MXR-1]]<=a[i])MXR--;QMX[MXR++]=i;
if(i<m)continue;
if(i>=2*m){
while(fl!=fr&&f[qf[fr-1]]>=f[i-m])fr--;qf[fr++]=i-m;
// printf("<%d,%d>\n",fl,fr);
while(fl!=fr){
while(mnl!=mnr&&qmn[mnl]<=qf[fl])mnl++;
while(mxl!=mxr&&qmx[mxl]<=qf[fl])mxl++;
if(a[qmx[mxl]]-a[qmn[mnl]]<f[qf[fl]])break;
P=qf[fl++];
}
while(MNL!=MNR&&QMN[MNL]<=P)MNL++;
while(MXL!=MXR&&QMX[MXL]<=P)MXL++;
}
f[i]=a[QMX[MXL]]-a[QMN[MNL]];
if(fl!=fr)f[i]=min(f[i],f[qf[fl]]);
}
for(int i=1;i<=n;i++)write(f[i]),putc('\n');
print_final();
return 0;
}