[DP记录]AT5142 [AGC035E] Develop
command_block
2021-04-30 10:36:56
**题意** ： 初始时，在黑板上写有 $-10^{18}$ 到 $10^{18}$ 中的所有整数。
每次你可以选中一个 $[1,n]$ 中还在黑板上的整数 $x$ ，把它擦去并补写上 $x-2$ 与 $x+k$ （如果原来不存在的话）。
你可以进行这个操作任意次（可以不进行），求最终黑板上数字的可能状态有多少种，答案对给定整数 $m$ 取模。
$k\leq n\leq 150$ ，时限$\texttt{5s}$。
------------
考虑如何判定一种状态能否达到。
若最终 $x$ 不在黑板上，则 $x$ 一定要后于 $x+2$ 与 $x-k$ 被擦去，因为两者被擦去时会写回 $x$。
于是，连边 $x+2\rightarrow x$ 和 $x-k\rightarrow x$ ，这个有向图的每一个拓扑序都是一种合法的擦除方案，若有向图中有环，则无解。
现在问题能转化为 ： 问 $[1,n]$ 的多少个子集形成的有向图是无环的。
先把 $[1,n]$ 的完整图画出来，观察会产生怎样的环 ：
（from @关怀他人）（这张图是 $k$ 为奇数的情况）
将奇数和偶数分别画成两排。（记偶数集合为 $Z_0$ ，奇数集合为 $Z_1$）
- 若 $k$ 为偶数，则在一排中选择达到 $k/2+1$ 个连续的数，就会形成环。
两条链互不干涉，方案数是乘起来的。对于每条链分别简单 $\rm DP$ 即可。
- 若 $k$ 为奇数，则如上图。将 $x\rightarrow x+k$ 的边画在两条链中间。
不难发现，只需要考虑那些含有两条横边的环。
所有的环都形如 ： 从左侧某个点开始，向上走一段，向右走一次，向上走一段，回到原点。
如图中 $5\rightarrow 3\rightarrow 6\rightarrow 4\rightarrow 2\rightarrow 5$。
考虑 $\rm DP$ 。设 $dp[i][j][k]$ 表示考虑了前 $i$ 层（如图中横着的边），最长上右上路径长度达到 $j$ ，右侧偶数链连续选数 $k$ 个的方案数。
若 $j$ 达到 $k+2$ ，则会产生一个环。
选中左侧奇数，可以延续右上右路径（前提是得有）
当左侧奇数不选时，会切断上右上路径。
当左侧奇数和右侧偶数同时选中时，会产生新的右上右路径，长度为 $k+1$。
具体转移见代码。
复杂度 $O(n^2k)$。
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
int n,t,mod,f[82][155][82],g[82][82],pw2[82];
int main()
{
scanf("%d%d%d",&n,&t,&mod);
if (t&1){
pw2[0]=1;
for (int i=1;i<(t/2);i++)pw2[i]=(pw2[i-1]<<1)%mod;
for (int i=0;i<=(t/2);i++)
f[0][0][i]=pw2[max((t/2)-i-1,0)];
for (int i=1;2*i-1<=n;i++){
if (2*i-1+t<=n){
for (int j=0;j<=t+1;j++)
for (int k=0;k<=n/2;k++)
if (f[i-1][j][k]){
int sav=f[i-1][j][k];
if (j>0){
f[i][0][0]=(f[i][0][0]+sav)%mod;
f[i][0][k+1]=(f[i][0][k+1]+sav)%mod;
f[i][j+1][0]=(f[i][j+1][0]+sav)%mod;
f[i][j+1][k+1]=(f[i][j+1][k+1]+sav)%mod;
}else {
f[i][0][0]=(f[i][0][0]+2ll*sav)%mod;
f[i][0][k+1]=(f[i][0][k+1]+sav)%mod;
f[i][k+2][k+1]=(f[i][k+2][k+1]+sav)%mod;
}
}
}else {
for (int j=0;j<=t+1;j++)
for (int k=0;k<=n/2;k++)
if (f[i-1][j][k]){
int sav=f[i-1][j][k];
if (j>0){
f[i][0][0]=(f[i][0][0]+sav)%mod;
f[i][j+1][0]=(f[i][j+1][0]+sav)%mod;
}else f[i][0][0]=(f[i][0][0]+2ll*sav)%mod;
}
}
}
int ans=0;
for (int j=0;j<=t+1;j++)
for (int k=0;k<=n/2;k++)
ans=(ans+f[(n+1)/2][j][k])%mod;
printf("%d",ans);
}else {
g[0][0]=1;t/=2;
for (int i=0;i<(n+1)/2;i++)
for (int j=0;j<=min(i,t);j++){
if (j+1<=t)
g[i+1][j+1]=(g[i+1][j+1]+g[i][j])%mod;
g[i+1][0]=(g[i+1][0]+g[i][j])%mod;
}
int ans1=0,ans2=0;
for (int i=0;i<=t;i++){
ans1=(ans1+g[n/2][i])%mod;
ans2=(ans2+g[(n+1)/2][i])%mod;
}printf("%lld",1ll*ans1*ans2%mod);
}return 0;
}
```