题解：P7519

· · 题解

来一个 naive 的做法。

首先考虑 n! 级别的做法，考虑枚举一种排列，然后检验是否合法。

具体的，我们发现，如果 m 道题没有分完，可以直接分给最后一个人，也就是说，我们可以依次贪心的给每个人最少的题，使得比其他所有人都高，时间复杂度 O(n!\times n) 。

我们发现，除了第一个人以外，其他所有人只要满足比前一个人高即可，第一个人要比其他所有人都高，于是可以做到 O(n!)，但似乎区别不大。

我们发现，m 很小，除 1 外 b_i 只与且最终的 b_{i-1} 和 a_{i-1} 有关，排列中 b_i=max(b_{i-1},a_{i-1}+b_{i-1}-a_i)，换句话说，每当 b_{i-1} 增加 1，b_i 一定增加 1。

这提示我们，可以直接上 Meet-in-Middle，枚举后一半，再枚举前一半合并，假设前一半的最后一个 b 是 x，相当于后面所有数的 b 都要加上 x。

暴力前缀和的总复杂度是 O(A_{n}^{(n+1)/2}\times n+2^n\times n\times m)。

如果你用树状数组维护前缀和可以做到 O(A_{n}^{(n+1)/2}\times n\times \log m)，在这道题不优。但 m 可以出的更大

#include<bits/stdc++.h>
using namespace std;
int read(){
    int t=0;char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
int n,p[15],a[15],m,b[15],LMT,f[8195][15][502];
bool v[15];
long long ans;
void dfs(int x,int y){
    if(x==LMT+1){
        int zt=0;
        for(int i=1;i<x;++i)zt|=(1<<p[i]-1);
        ++f[zt][p[1]][y];
        return;
    }
    int mx=-1;
    for(int i=1;i<=n;++i)
        if(!v[i]){
            int dlt=a[p[x-1]]+b[x-1]-a[i];
            if(p[x-1]<i)++dlt;
            mx=max(mx,a[i]);
            if(dlt<b[x-1])dlt=b[x-1];
            if(y+dlt>m)continue;
            b[x]=dlt,p[x]=i,v[i]=1,dfs(x+1,y+dlt),v[i]=0;
        }
}
void dfs1(int x,int y){
    if(x==LMT+1){
        int zt=0,B=(1<<n)-1;
        for(int i=1;i<x;++i)zt|=(1<<p[i]-1);
        B^=zt;
        for(int i=1;i<=n;++i)
            if(B&(1<<(i-1))){
                int dlt=a[p[x-1]]+b[x-1]-a[i];
                if(p[x-1]<i)++dlt;
                if(dlt<b[x-1])dlt=b[x-1];
                dlt=max(dlt,0);
                int ss=dlt*(n-LMT)+y;
                if(ss<=m)ans+=f[B][i][m-ss];
            }
        return;
    }
    int mx=-1;
    for(int i=1;i<=n;++i)
        if(!v[i]){
            int dlt=a[p[x-1]]+b[x-1]-a[i];
            if(p[x-1]<i)++dlt;
            if(x==1){dlt=max(dlt,mx-a[i]+1);for(int j=i+1;j<=n;++j)if(!v[j])dlt=max(dlt,a[j]-a[i]);}
            mx=max(mx,a[i]);
            if(dlt<b[x-1])dlt=b[x-1];
            if(y+dlt>m)continue;
            b[x]=dlt,p[x]=i,v[i]=1,dfs1(x+1,y+dlt),v[i]=0;
        }
}
int main(){
    n=read(),m=read(),a[0]=-1e9;
    for(int i=1;i<=n;++i)a[i]=read(),p[i]=i;
    LMT=n>>1;
    dfs(1,0);
    for(int i=0;i<(1<<n);++i)for(int j=1;j<=n;++j)for(int k=1;k<=m;++k)f[i][j][k]+=f[i][j][k-1];
    LMT=(n+1)>>1;
    dfs1(1,0);
    printf("%lld",ans);
}