题解：P11216 【MX-J8-T4】 2048

· · 题解

好玩的题目。

不妨设当前局面的第 i 个数为 2^{a_i}，是第 t_i 个出现的。

此时 a 一定是单峰的，由定义知对于峰值的任一侧而言不存在等值点。

证明：考虑归纳，发现操作不改变单峰的性质。

下记 pa 表示 a 的最大值的位置。

考虑 t 的性质，先考虑最小值所在位置 pt，发现能取的值很少。

首先 pa=pt 时，可以发现（归纳）此时 t 是单谷的。

否则，就只能通过不断往一侧加数来刷新 t_{pa}，可知此时 |pa-pt|=1 且 t 单谷，由于是刷新 t_{pa}，故还要求 a_{pt}+1<a_{pa}。

同时，要考虑当前的空格是否够我们合成出 a，可得 n+1-t_i\ge a_i。

现在我们已经推出了 a 和 t 的性质，考虑计数，对于这个题而言，DP 无疑是更好的选择。

单峰的序列一般有如下的刻画方式：

1.拆成两个递增序列。

2.区间 DP，按值的从大（小）到小（大）。

第一种不好处理 t_i 和 a_i 的关系，考虑第二种，把峰值去掉，按 t 从大到小做。

记 f_{n,a1,a2} 表示已经确定了 n 个数，左边极值为 a1，右边极值为 a2 的方案数。

初始 f_{0,0,0}=0，转移是 f_{i,j,k}=\sum\limits_{a=0}^{j-1}f_{i-1,a,k}+\sum\limits_{a=0}^{k-1}f_{i-1,j,a}，前缀和优化一下就是 O(n^3)。（为满足 a，t 的关系要求 j,k\le i）

考虑算答案，设 g_{i,j} 表示 n=i，最大值恰为 j 的答案。

最后对 g 求前缀和就可以 O(1) 回答了。

总复杂度 O(nx^2+T)。

代码：

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define bi __int128_t
#define lb(x) ((x)&(-(x)))
#define gp(i,j) (((i)>>(j-1))&1)
#define ppc __builtin_popcount
using namespace std;
const int N=305;//mod=1e9+7;
const ll inf=1e18+10;
int mod,n,k,LM=303;
void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
void Sub(int &a,int b){a-=b;if(a<0) a+=mod;}
void Mul(int &a,int b){a=1ll*a*b%mod;}
int qp(int a,int b){
    int x=1;
    while(b){
        if(b&1) Mul(x,a);
        Mul(a,a);b>>=1;
    }return x;
}
int f[N][N][N],sum1[N][N][N],sum2[N][N][N],ans[N][N];
void slv(){
    cin>>n>>k;
    int o=n/2+1;
    cout<<ans[n][k-1]<<endl;
}
int main(){
    int t=1;cin>>t>>mod;
    f[0][0][0]=1;
    for(int i=0;i<=LM;i++) sum1[0][i][0]=1,sum2[0][0][i]=1;
    for(int i=1;i<=LM;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=i;k++){
                if(j!=0) Add(f[i][j][k],sum1[i-1][j-1][k]);
                if(k!=0) Add(f[i][j][k],sum2[i-1][j][k-1]);
                sum1[i][j][k]=f[i][j][k];
                sum2[i][j][k]=f[i][j][k];
                //if(i<=5) cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<endl;
            }
        }for(int j=0;j<=i;j++){
            for(int k=1;k<=i;k++){
                Add(sum1[i][k][j],sum1[i][k-1][j]);
                Add(sum2[i][j][k],sum2[i][j][k-1]);
            }
        }
    }for(int i=1;i<=LM;i++){
        for(int j=1;j<=LM;j++){
            ans[i][j]=ans[i][j-1];
            if(j<=i){
                for(int k=0;k<=j-1;k++){
                    Add(ans[i][j],sum2[i-1][k][j-1]);
                }
                for(int k=1;k<=j-2;k++){
                    Add(ans[i][j],sum1[i-1][k-1][j]);
                    Add(ans[i][j],sum2[i-1][j][k-1]);
                }
            }
            //if(i==1) cout<<i<<' '<<j<<' '<<ans[i][j]<<endl;
        }
    }
    while(t--) slv();
    return 0;
}