CF1670F Jee, You See

CF1670F Jee, You See?

Description

给定 4 个整数 $n,l,r,z$ $1 \le n \le 1000,1 \le l \le r \le 10^{18},1 \le z \le 10^{18}$

求满足一下条件的序列 $a$ 的个数：

1. $a_i$ 为非负整数
2. $l \le a_1 + a_2 + \dots a_n \le r $
3. $a_1 \oplus a_2 \oplus \dots \oplus a_n = z$

其中 $\oplus$ 表示二进制按位异或运算

答案对 $10^9 + 7$ 取模

2s 250MB

Solution

令 $\sum a_i\le r$ 且符合题意的个数为 $G(r)$ ，则答案为 $G(r)-G(l-1)$。转化为求 $1\le \sum a_i\le r$ 的个数。

考虑数位 dp ，令 $f[i][j]$ 表示从低到高第 $i$ 位，还能以 $2^i\times j$ 填剩下的位数。

令 $x=2j+\text{[n第 i 位为1]}$，转移是 $f[i][x-t]\Leftarrow f[i+1][j]\dbinom{n}{t}$

考虑到从低到高第 $i$ 位之和最大只有 $(2^i-1)n$，所以第二位最大只有 $n$。

转移的时候考虑一下 $z$ 的限制即可。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,L,R,z;
const int mod=1e9+7;
int dp[65][1005],c[1005][1005];
inline void add(int &x,int y) {x=(x+y)%mod;}
inline int solve(int m) {
	int i,j,t;
	memset(dp,0,sizeof(dp));
	dp[63][0]=1;
	for (j=62;j>=0;j--) {
		for (i=0;i<=n;i++) {
			int now=2*i+(m>>j)%2;
			for (t=(z>>j)%2;t<=min(now,n);t+=2)
				add(dp[j][min(now-t,n)],dp[j+1][i]*c[n][t]);
		}
	}
	int ans=0;
	for (i=0;i<=n;i++) add(ans,dp[0][i]);
	return ans;
}
signed main(void){
	int i,j;
	read(n);read(L);read(R);read(z);
	c[0][0]=1;
	for (i=1;i<=n;i++) {
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	printf("%lld",(solve(R)-solve(L-1)+mod)%mod);
	return 0;
}