正题

题目链接:https://www.luogu.com.cn/problem/P7519

题目大意

\(n\)个队伍，队伍之间按照得分从小到大排名，得分相同的按照编号从小到大排。开始时每个队伍有个初始得分\(a_i\)，和一个额外分\(b_i\)，主持人会按照\(b_i\)不降的顺序让每个队伍的得分加上\(b_i\)，并且要求每次加上后这个队伍都变成第一名。

已知每个队伍的初始分\(a\)和额外分的和\(m\)，求有多少种公布额外分的序列。

\(1\leq n\leq 13,1\leq m\leq 500,0\leq a_i\leq 10^4\)

解题思路

显然地一点是我们考虑一个序列合法时\(b_i\)的和的最小值，然后和\(m\)进行比较

开始思路时卡了，假设已经排好了一部分，我们需要把一个新的排在后面，此时会有两个限制：

1. 这个队伍的得分\(a_i+b_i\)必须是已经公布的里面最大的（或相同的序号最小的）
2. \(b_i\)必须是已经公布的里面最大的。

显然记录上这两个限制进行的\(dp\)并不方便，考虑如何去掉一个限制，因为\(b_i\)是我们可以任意调整的，并且要求递增，可以每次操作都让后面所有数字的\(b_i\)都同时加值，这样就不需要考虑第二个限制了。

然后是第一个限制如何处理，注意到我们在刚刚的情况下，假设限制最后公布的一个是\(i\)，而下一个公布的是\(j\)，那么此时有\(b_j=b_i\)，所以此时两个数加上\(b\)之后的差值不变，所以直接拿\(a_i-a_j\)就可以知道后面的\(b_j\)要加上多少了。

那么做法已经显然了，设\(f_{s,i,j}\)表示现在已经插入的数状态为\(s\)，\(b_i\)的和为\(i\)，目前最后一个公布的是\(j\)，然后\(O(n)\)转移即可。

时间复杂度：\(O(2^nmn^2)\)，实际上很多状态是不会到达的，所以能过。

code

#include
#include
#include
#define ll long long
using namespace std;
const ll N=13;
ll n,m,ans,a[N],c[1<a[pos])pos=i;
	}
	f[0][0][pos]=1;
	ll MS=(1<>j)&1)continue;
					ll w=max(a[i]-a[j]+(j>i),0ll)*(n-c[s]);
					if(k+w>m)continue;
					f[s^(1<