题意
设 \(f(a,b)=\sum_{i=0}^b\binom{b}{i}\binom{n-i}{a}\)，对所有 \(1\le a,b\le m\) 求出 \(f(a,b)\) 的异或和。
\(n\le 10^9,m\le \min(n,5000)\)
分析
显然异或没有任何性质，你需要求出所有 \(f(a,b)\)。发现这个东西本身也很难求，考虑递推：
\[f(a,b)=\sum_{i=0}^b \left[\binom{b-1}{i}+\binom{b-1}{i-1}\right]\binom{n-i}{a}=\sum_{i=0}^b \binom{b-1}{i}\binom{n-i}{a}+\sum_{i=0}^b\binom{b-1}{i-1}\binom{n-i}{a}=f(a,b-1)+\sum_{i=0}^b\binom{b-1}{i-1}\binom{n-i}{a}
\]
考虑将后一部分进一步拆分：
\[\sum_{i=0}^b\binom{b-1}{i-1}\binom{n-i}{a}=\sum_{i=0}^b\binom{b-1}{i-1}\left[\binom{n-i+1}{a+1}-\binom{n-i}{a+1}\right]=\sum_{i=0}^{b-1}\binom{b-1}{i}\binom{n-i}{a+1}-\sum_{i=0}^{b-1}\binom{b-1}{i}\binom{n-i-1}{a+1}=f(a+1,b-1)-\sum_{i=0}^b\binom{b-1}{i}\binom{n-i-1}{a+1}
\]
设 \(g(a,b)=\sum_{i=0}^b\binom{b}{i}\binom{n-i-1}{a}\)，那么最终 \(f\) 有递推式
\[f(a,b)=f(a,b-1)+f(a+1,b-1)-g(a+1,b-1)
\]
注意到：
\[f(a,b)=\sum_{i=0}^b\binom{b}{i}\binom{n-i}{a}=\sum_{i=0}^b\binom{b}{i}\binom{n-i-1}{a}+\sum_{i=0}^b\binom{b}{i}\binom{n-i-1}{a-1}=g(a,b)+g(a-1,b)
\]
虽然此时已经能通过递推求解 \(f,g\) 了，但是我们可以将递推式化成只与 \(f\) 有关的形式：
\[f(a,b)+f(a+1,b)
\]
\[=f(a,b-1)+f(a+1,b-1)+f(a+1,b-1)+f(a+2,b-1)-g(a+1,b-1)-g(a+2,b-1)
\]
\[=f(a,b-1)+f(a+1,b-1)+f(a+1,b-1)+f(a+2,b-1)-f(a+2,b-1)
\]
\[=f(a,b-1)+2f(a+1,b-1)
\]
最终得到：
\[f(a,b)=f(a,b-1)+2f(a+1,b-1)-f(a+1,b)
\]
直接递推，复杂度 \(O(n^2)\)。边界预处理的复杂度也是容易做到 \(O(n^2)\) 的。
int n,m;
int f[maxn][maxn];
int inv[maxn];
int Combine(int x,int y){if(x<y)return 0;int res=1;rep(i,x-y+1,x)res=res*i%mod;rep(i,1,y)res=res*inv[i]%mod;return res;
}
int D[maxn];
int C[maxn][maxn];
inline void solve_the_problem(){n=rd(),m=rd();inv[1]=1;rep(i,2,m)inv[i]=inv[mod%i]*(mod-mod/i)%mod;rep(i,0,m)D[i]=Combine(n-i,m);C[0][0]=1;rep(i,1,m){C[i][0]=1;rep(j,1,m)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}rep(b,0,m)rep(i,0,b)adder(f[m][b],C[b][i]*D[i]%mod);rep(a,0,m)f[a][0]=Combine(n,a);per(a,m-1,1)rep(b,1,m)f[a][b]=(f[a][b-1]+2*f[a+1][b-1]-f[a+1][b]+mod)%mod;int ans=0;rep(i,1,m)rep(j,1,m)ans^=f[i][j];write(ans);
}