题解：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$ 可以出的更大~~ ```cpp #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); } ```