题解：CF295D Greg and Caves / [SNOW] - 73

· · 题解

*2400 调一万年我有救了。

这个玩意是对称的，考虑确定 t 然后独立的数某一侧的方案数。

考虑到这个方案数依赖于上一行的长度，并且注意到我们知道向上扩展 i 个以后就能转移出向上扩展 i+1 个的方案，于是可以 dp，以长度和向上扩展的距离作为下标，最后对这个东西进行统计就做完了。

假了，假一万年。

终于你发现如果这个洞中间一段长度完全相同的时候有多个 t 符合条件，于是假完了。

如何去重？我们钦定符合条件的 t 一侧必须长度严格小于。

那么我们这个时候的方案就是原先 dp 的转移数组上长度维度减一得到的位置上的方案数……吗？

假了，再假一万年。

注意到这个时候的意义等价于废掉一个固定的点不可使用，但这个显然会少算。

事实上是存在这个边界上的点产生贡献的方案的。

那么我们只需要再写一遍 dp 转移出必然使用这个废点的方案数加回去就做完了。

然后你发现这样做会是 O(n^3) 的。

然后你又注意到这两轮 dp 都可以上前缀和优化，于是时间复杂度 O(n^2)。

转移方程顺着意义就可以推出来，难点不在这里可以直接看代码。

#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
int dp[2005][2005];
int sum[2005][2005];
int dp2[2005][2005];
void solve(){
    int n,m;
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)
    ans=(ans+(m-j+1)*dp[i-1][j]%mod*((dp[n-i][j-1]+dp2[n-i][j-1])%mod)%mod)%mod;
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n=2000;
    for(int i=0;i<=n;i++)
    dp[0][i]=1;
    for(int j=2;j<=n;j++)sum[0][j]=dp[0][j];
    for(int j=3;j<=n;j++)sum[0][j]=(sum[0][j-1]+sum[0][j])%mod;
    for(int j=3;j<=n;j++)sum[0][j]=(sum[0][j-1]+sum[0][j])%mod;
    for(int i=1;i<=n;i++){
        for(int j=2;j<=n;j++)
        dp[i][j]=(dp[i][j]+sum[i-1][j])%mod;
        for(int j=0;j<=n;j++)dp[i][j]++;
        for(int j=2;j<=n;j++)sum[i][j]=dp[i][j];
        for(int j=3;j<=n;j++)sum[i][j]=(sum[i][j-1]+sum[i][j])%mod;
        for(int j=3;j<=n;j++)sum[i][j]=(sum[i][j-1]+sum[i][j])%mod;
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=n;j++)
        dp2[i][j]=(dp2[i][j-1]+dp[i-1][j]%mod)%mod;
    }
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
// 面包店的老板也说：
//「啊啊，魔女小姐。你也看到了吧？那孩子每次都拿那种东西来买面包。我知道她很可怜——不过我们也是做生意的，不知道该怎么办啊。」

我觉得有紫啊，每假一次都得手玩好久的 hack 然后再改，改对另说改错就再瞪一万年，而且边界的分讨需要仔细，上前缀和优化的时候不小心写挂点东西又要重构，一整个数哭出来了。到底简单在哪 T_T

万人血书请求升紫（1 / 10000）