P5241 序列（滚动数组+前缀和优化dp）

P5241 序列

挺神仙的一题

看看除了dp好像没什么其他办法了

想着怎么构个具体的图出来，然鹅不太现实。

于是我们想办法用几个参数来表示dp数组

加了几条边肯定要的吧，于是加个参数$i$表示已加了$i$条边

这显然是不够的。于是我们又想：强连通分量.....连通块.......

于是加个$j$表示还有$j$个强连通分量

于是dp数组为$f[i][j]$

这是我们发现一个问题，状态$f[i][j]$不一定是合法的。

那dp不就GG了吗

再次撕烤，我们发现每次加上的边无非就3种情况：

1.把2个强连通分量（或链）连成一条链

2.在某个强连通分量中瞎连（没啥用）

3.在1条链上的某点向回连，形成一个环，缩成一个新强连通分量（可以减少任意个强连通分量）

我们设$k-1$条边（dp数组下标$k$为正数较好处理）投入到第3种情况

要生成剩下$j$个强连通的情况，我们最少投入$n-j$条边用于第1种情况

所以$n-j+(k-1)<=i$

我们又发现，要生成剩下$j$个强连通的情况，我们最多共投入的边数$i$是有限制的

最多情况就是1个块有$n-j+1$个点，剩下$j-1$个块只有1个点，蓝后大块每个点连$n-1$条边，小块互相之间弱连通

那么最大边数为$(n-j+1)*(n-1)+(j-2+j-3+j-4+...+1)=(n-j+1)*(n-1)+(j-1)*(j-2)/2$

所以$i<=(n-j+1)*(n-1)+(j-1)*(j-2)/2$

总结一下，即设$f[i][j][k]$表示到第$i$条边，有$j$个强连通分量，$k-1$条边向回连的方案数

限制条件：

$n-j+(k-1)<=i$

$i<=(n-j+1)*(n-1)+(j-1)*(j-2)/2$

转移：

$f[i][j][k]+=f[i-1][j][k]$（第2种情况）

$f[i][j][k]+=\sum_{h=j+1}^{n}f[i-1][h][k-1]$

显然是可以滚动数组+前缀和优化的辣

然鹅复杂度还是太高，主要因为k很麻烦

仔细观察k，发现

$n-j+(k-1)<=i$

$k<=i+j-n+1$

发现$i>=2n$时k总是合法的

于是我们就可以愉快地缩成2维辣

#include<iostream>

#include<cstdio>

#include<cstring>

#define rint register int

using namespace std;

inline int Min(int a,int b){return a<b?a:b;}

const int mod=1e9+;

inline int Md(int x){return x<mod?x:x-mod;}

#define N 405

int n,f[][N][N],sf[][N][N],g[][N],sg[N][N],lim[N],ans[N*N];

int main(){

    scanf("%d",&n); int tn=Min(n*(n-),n<<),w=;

    for(rint j=;j<=n;++j) lim[j]=(n-j+)*(n-)+(j-)*(j-)/;

    f[][n][]=ans[]=;

    for(rint j=;j<=n;++j) sf[][n][]=;

    for(rint i=;i<=tn;++i,w^=){

        for(rint j=;j<=n;++j)

            for(rint k=;k<=n;++k)

                f[w][j][k]=;

        for(rint j=;j<=n;++j) if(lim[j]>=i)

            for(rint k=;k<=n;++k) if(i-(k-)>=n-j)

                f[w][j][k]=Md(f[w^][j][k]+sf[w^][j+][k-]);

        for(rint j=n;j;--j)

            for(rint k=;k<=n;++k){

                sf[w][j][k]=Md(sf[w][j+][k]+f[w][j][k]);

                ans[i]=Md(ans[i]+f[w][j][k]);

            }

    }w=;

    for(rint j=;j<=n;++j)

        for(rint k=;k<=n;++k)

            g[][j]=Md(g[][j]+f[][j][k]);

    for(rint j=n;j;--j) sg[][j]=Md(sg[][j+]+g[][j]);//降维

    for(rint i=tn+;i<=n*(n-);++i,w^=){

        for(rint j=;j<=n;++j) g[w][j]=;

        for(rint j=;j<=n;++j) if(lim[j]>=i)

            g[w][j]=Md(g[w^][j]+sg[w^][j+]);

        for(rint j=n;j;--j){

            sg[w][j]=Md(sg[w][j+]+g[w][j]);

            ans[i]=Md(ans[i]+g[w][j]);

        }

    }

    for(rint i=;i<=n*(n-);++i) printf("%d ",ans[i]);

    return ;

}

巴特西

P5241 序列（滚动数组+前缀和优化dp）

最新文章

热门文章