P11216 【MX-J8-T4】2048 题解

· · 题解

这是本蒟蒻的第一篇正式题解。

本题重点在于找到无解序列的充要条件，首先记 a_i 为游戏结束时第 i 个数取 2 的对数，t_i 为第 i 个数出现时间离散化后的值，显然 a 相邻两项不同，t 是一个排列，如果一个位置比它相邻位置大且出现时间小，直接按照顺序合成即可，如果一个元素比它相邻位置小且出现时间小呢？我们可以先合成较大数的一半再合成较小数，最后合成较大数，具体参考样例解释中 [2,8,4,2] 的第四种情况。

一些性质

  3. 若 t_i<t_{i+1}，那么 a_i+1\ne a_{i+1}，这是因为如果 a_i+1=a_{i+1}，那么 a_{i+1} 的合成会影响到 a_i 的合成。同理，若 t_i<t_{i-1}，那么 a_i+1\ne a_{i-1}。

  4. 若 t_{i-1}<t_i<t_{i+1}，那么不可能会有 a_{i-1}<a_i<a_{i+1}，这是因为如果 a_{i-1}<a_i<a_{i+1}，那么首先要合成 a_{i+1}-1，然后合成 a_i-1，最后合成 a_{i-1}，这会使 a_i-1 无法进一步合成出 a_i。同理，若 t_{i-1}>t_i>t_{i+1}，那么不可能会有 a_{i-1}>a_i>a_{i+1}。

我们容易发现，这些性质已经充要，我们来考虑如何 dp。

DP

考虑到性质 1 和性质 4，可以发现出现时间最小的位置只能是 a 中最大的位置或这个位置的相邻两个位置，也就是下图中红框框住的点。也就是说出现时间最小的位置的两边元素大小分别是单增和单减，因此我们可以按照出现时间从大到小进行转移。

设 F_{i,L,R} 表示已经有 i 个数确定，其中左块最右边的数是 L，右块最左边的数是 R，首先考虑 L 与 R 的范围。假设格子总数是 m，第 j 个转移的数大小为 x，根据性质 2 有：x+m-j\le m ，也就是 x\le j，因此有 L\le i，R\le i。转移方程为：F_{i,L,R}=(\sum_{[tl\lt L]}F_{i-1,tl,R} )+(\sum_{[tr\lt R]}F_{i-1,L,tr} )，这个东西可以用前缀和优化，贡献答案时差分即可，时间复杂度 O(300^3+T)。

AC Code

#include<bits/stdc++.h>
using namespace std;
int T,mod,n,x,dp[305][305][305],f[305][305][305],g[305][305][305],sum[305][305];
void add(int &x,int y){
    (x+=y)%=mod;
}
void fun(int n,int lx,int rx,int res){//计算贡献
    add(sum[n][lx],res),add(sum[n][rx+1],mod-res);
}
int main(){
    scanf("%d%d",&T,&mod);
    dp[0][0][0]=g[0][0][0]=f[0][0][0]=1,fun(1,1,1,1);
    for(int i=1;i<300;i++)
        for(int j=0;j<=i;j++)
            for(int k=0;k<=i;k++)if(j+k){
                if(j)add(dp[i][j][k],f[i-1][j-1][k]);
                if(k)add(dp[i][j][k],g[i-1][j][k-1]);
                f[i][j][k]=g[i][j][k]=dp[i][j][k],fun(i+1,max(j,k)+1,i+1,dp[i][j][k]);
                if(j+1<=k-2)fun(i+1,k,k,dp[i][j][k]*2LL*((k-2)-(j+1)+1)%mod);   //考虑到对称性直接*2即可
                if(j)add(f[i][j][k],f[i][j-1][k]);
                if(k)add(g[i][j][k],g[i][j][k-1]);
            }
    for(int i=1;i<=300;i++)for(int j=1;j<=300;j++)add(sum[i][j],sum[i][j-1]);
    for(int i=1;i<=300;i++)for(int j=1;j<=300;j++)add(sum[i][j],sum[i][j-1]);
    while(T--)scanf("%d%d",&n,&x),printf("%d\n",sum[n][x-1]);
    return 0;
}

如有表达不清可以在评论区里交流讨论。