题解：CF1943D1 Counting Is Fun (Easy Version)

· · 题解

前言

卡常！不要带longlong！写的不好会TLE！

O(N^4)暴力

思路

这种题直接用填表法容易消耗巨量脑细胞，这里使用刷表法来推式子。

首先我们会想到这种题常见的DP状态是 f_{i,j} 表示DP到了 i 处并且目前有 j 次操作区间的右端点在 j 点。不过因为题目中划定每次操作区间的长度不得为 1，我们可以加一维处理目前有多少个操作区间的右端点刚好就是其左端点。最终的定义状态就是 f_{i,j,k} 表示DP到前 i 个其中右端点在 i 的操作区间中有 j 个长度为 1，k 个长度大于等于 2。

不过这样定义状态会有重复计算的问题，详细说就是我们有两种不同的操作方式却可以让同一个数列变成全零，这时候答案就会计算两次。解决方法也很简单，只要规定数列中下一个数字先用原来长度为 1 的操作序列来填充，再用长度大于等于 2 的来填充，如果还是填充不完就新开几个操作序列来填充。

转移在代码里。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=405;
int n,m,mod;
int f[N][N][N];//f[i][j][k]表示到i了，有j个长度为1的k个长度大于等于2的
void update(int h,int a,int b,int c,int d,int w){
    f[h][a][b]=(f[h][a][b]+w)%mod;
    f[h][c+1][b]=(f[h][c+1][b]-w+mod)%mod;
    f[h][a][d+1]=(f[h][a][d+1]-w+mod)%mod;
    f[h][c+1][d+1]=(f[h][c+1][d+1]+w)%mod;
}
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n>>m>>mod;
        for(int i=0;i<=n+2;i++)for(int j=0;j<=n+2;j++)for(int k=0;k<=n+2;k++)f[i][j][k]=0;
        f[0][0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=m;k++){
                    for(int nx=j;nx<=m;nx++){//枚举的是数列中下一个数字是什么
                        int _1=max(0ll,nx-(j+k)),_2=min(j+k,nx);
                        f[i+1][_1][_2]=(f[i+1][_1][_2]+f[i][j][k])%mod;
                    }
                }
            }
        }
        int ans=0;
        for(int k=0;k<=m;k++)ans=(ans+f[n][0][k])%mod;
        cout<<ans<<"\n";
    }

    return 0;
}

正解

优化

发现对于每个 f_{i,j,k} 转移到的位置类似下图标红位置：

那显然可以前缀和优化。

Code

#include<bits/stdc++.h>
using namespace std;
//#define int long long一定不要加，不然会TLE
const int N=405;
int n,m,mod;
int f[N][N][N];//f[i][j][k]表示到i了，有j个长度为1的k个长度为2的
void push(int &a,int b){//此优化疑似没有P用
    a+=b;
    if(a>=mod)a%=mod;
    if(a<0)a+=mod;
}
void update(int h,int a,int b,int c,int d,int w){
    push(f[h][a][b],w);
    push(f[h][c+1][b],-w);
    push(f[h][a][d+1],-w);
    push(f[h][c+1][d+1],w);
}
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n>>m>>mod;
        for(int i=0;i<=n+2;i++)for(int j=0;j<=n+2;j++)for(int k=0;k<=n+2;k++)f[i][j][k]=0;
        f[0][0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k<=m;k++){
                    if(!f[i][j][k])continue;
                    int l=j,r=min(m,j+k);
                    update(i+1,0,l,0,r,f[i][j][k]);
                    l=1;r=m-(j+k);
                    if(l<=r){
                        update(i+1,l,j+k,r,j+k,f[i][j][k]);
                    }
                }
            }
            for(int j=0;j<=m;j++){
                for(int k=0;k<=m;k++){
                    if(j!=0)push(f[i+1][j][k],f[i+1][j-1][k]);
                    if(k!=0)push(f[i+1][j][k],f[i+1][j][k-1]);
                    if(j!=0&&k!=0)push(f[i+1][j][k],-f[i+1][j-1][k-1]);

                }
            }
        }
        int ans=0;
        for(int k=0;k<=m;k++)ans=(ans+f[n][0][k])%mod;
        cout<<ans<<"\n";
    }
    return 0;
}