模拟赛 circle 题解

题意：有N个数，问有多少个x，\((x\leq T)\)，满足这N个数分别+x后，异或和为S。每个数小于\(2^M\)。
数位DP。
由于是加法，需要记录进位，因此从低位到高位DP。
只要记录下有几个进位，就可以根据这N的数的大小知道究竟是哪几个进位了。
设\(dp(i,j,0/1)\)表示考虑到第i位，有j个进位，与T的大小关系为0/1的方案数。
可以提前预处理出转移，即\(g(i,j,0/1)\)表示考虑到第i位，有j个进位，当前位使用\(0/1\)造成的进位数。
时间复杂度\(O(NMlogN)\)（有排序），可以优化至\(O(NM)\)。
代码（未经优化）：

#include 
#include 
#define ll long long
struct SPx
{
	ll z;int i;
};
SPx px[52][100010];
ll sz[100010],dp[52][100010][2];
int sl[52][100010][2],tm[100010],ss[52];
int sgn(ll x)
{
	if(x>0)
		return 1;
	else if(x<0)
		return -1;
	return 0;
}
int cmp(const void*a,const void*b)
{
	return sgn(((SPx*)b)->z-((SPx*)a)->z);
}
ll solve(int m,int n,ll S,ll T)
{
	if(T==0)return 0;
	T-=1;
	for(int i=m;i>=0;i--)
	{
		int b=bool(S&(1ll<=0;j--)
			tm[j]=tm[j+1]+bool(sz[px[i-1][j].i]&(1ll<0)
				s0+=bool(sz[px[i-1][j-1].i]&(1ll<