自动搬运

查看原文

来自洛谷，原作者为

	determination 敬不完美的明天。

搬运于2025-08-24 22:52:55，当前版本为作者最后更新于2025-04-22 19:52:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

场上想了很久 dp 中的区间左右端点如果当成长度怎么排除在边上不能继续走的影响，后来发现自己是弱智。

首先这种计数题直接往 dp 去想，然后发现正着做要考虑覆盖，十分困难，所以考虑时光倒流，变成一个位置放上之后就不会再改变。

设 $f_{l,r,x,0/1}$ 为你的积木区间在 $[l,r]$，$x$ 放置在左端点或者右端点。那么转移是显然的。

我们发现这个 $l,r$ 的真正作用是限制左右转移不出界，那我不管界不就好了？

$f_{x,y}$ 表示积木区间长度为 $x$，最后一个块是 $y$，那么有：

$$f_{x,y}\to f_{x+1,y+1}$$（直接往旁边走） $$f_{x,y}\to f_{x+1,x+y}$$（走到另一边） $$f_{x,y}\to f_{x,y+2}$$（来回走，区间长度不会发生变化） 那么一个状态 $f_{x,n/n-1}$ 对答案的贡献就是 $2(m-x+1)f_{x,n/n-1}$（这个 2 是因为我们 dp 的时候没有考虑你最后一个在左边还是右边，另一个系数就是你把这段区间完整的放进最终序列的方案数），代码好写。 ```cpp #include #define int long long #define endl '\n' using namespace std; const int mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f; const int N=5e3+10,M=2e5+10; int f[N][N]; int n,m; inline void add(int &x,int y){x=(x+y)%mod;} signed main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin >> n >> m; f[2][2]=1; for ( int i = 2 ; i <= m ; i++ ) { for ( int j = 2 ; j <= n ; j++ ) { f[i][j]%=mod; add(f[i][j+2],f[i][j]); if(j+i<=n)add(f[i+1][j+i],f[i][j]); add(f[i+1][j+1],f[i][j]); } } int ans=0; for ( int i = 2 ; i <= m ; i++ ) add(ans,(f[i][n-1]+f[i][n])*(m-i+1)%mod); cout << ans*2%mod; return 0; } ```$$