$递归$递归

$正解部分$正解部分

$题目的几何意义:$题目的几何意义:
给出矩阵最上面一行和最左边一行, $(i,j)$(i,j)点的值为 $F[i,j]$F[i,j], $F[i,j]=F[i-1,j]⨁F[i,j-1]$F[i,j]=F[i−1,j]⨁F[i,j−1], 要求计算矩阵内的元素 .

假设现在要求点 $a:$a: $(x,y)$(x,y) 的答案, 上边界上的点 $b:$b: $(i,j)$(i,j) 对 $a$a 的贡献为

$C_{总步数}^{垂直距离}\mathrm{\&}1?F[x,y]:0$C总步数垂直距离​&1?F[x,y]:0

• 于是可以先利用已有条件求出 询问矩阵 $[2^k+1\to 2^k+100,2^k+1\to 2^k+100]$[2k+1→2k+100,2k+1→2k+100] 的 上, 下边界 ,
• 然后利用 $100\ast 100$100∗100 的 询问矩阵 上, 左边界预处理出整个矩阵, $O\left(1\right)$O(1) 处理询问即可 .

最坏时间复杂度 $O(2^{17}\ast 200+10^4)$O(217∗200+104) .

$注意上边界不能往右边走!!!!!!!!.所以对上边界,需要先向下走一步,再计算贡献,左边界同理$注意上边界不能往右边走!!!!!!!!.所以对上边界,需要先向下走一步,再计算贡献,左边界同理

$实现部分$实现部分

$如何得到组合数的奇偶:$如何得到组合数的奇偶:

设 $cnt\left[i\right]$cnt[i] 表示 $i!$i! 所包含的 $2$2因子 的个数, 然后阶乘计算组合数时只需看因子 $2$2的个数是否大于 $0$0 即可, 具体看代码.
同时还要注意 $cnt\left[\right]$cnt[] 数组要开 $2$2 倍 .

#include<bits/stdc++.h>
#define reg register

const int maxn = (1<<17) + 105;

int K;
int Q;
int top[maxn];
int cnt[maxn<<1];
int left[maxn];
int A[105][105];

int C(int n, int m){ return cnt[n]-cnt[m]-cnt[n-m]<=0; }

int main(){
        freopen("recursion.in", "r", stdin);
        freopen("recursion.out", "w", stdout);
        scanf("%d", &K); K = 1<<K;
        for(reg int i = 2; i <= 100+K; i ++) scanf("%d", &top[i]);
        for(reg int i = 2; i <= 100+K; i ++) scanf("%d", &left[i]);
        for(reg int i = 1; i <= (100+K)*2; i ++){ // --
                int tmp = i, tmp_2 = 0;
                while(!(tmp & 1)) tmp >>= 1, tmp_2 ++;
                cnt[i] = cnt[i-1] + tmp_2;
        }
// for(reg int i = 1; i <= 100; i ++) printf("%d\n", cnt[i]);
        /* for(reg int i = 1; i <= 100; i ++){ // a: (K+1, K+i) for(reg int j = 2; j <= K+i; j ++) // b: (1, j) A[1][i] ^= C(K+K+i-j-1, K-1)*top[j]; for(reg int j = 2; j <= K+i; j ++) // b: (j, 1) A[1][i] ^= C(K+K+i-j-1, K+i-2)*left[j]; } for(reg int i = 1; i <= 100; i ++){ // a:(K+i, K+1) for(reg int j = 2; j <= K+i; j ++) // b: (1, j) A[i][1] ^= C(K+i-1+K-j, K+i-2)*top[j]; for(reg int j = 2; j <= K+i; j ++) // b: (j, 1) A[i][1] ^= C(K+i-j+K-1, K-1)*left[j]; } */
        for(reg int i = 1; i <= 100; i ++){
                int tot = K - 1;
                for(reg int j = K+i; j >= 2; j --)
                        A[1][i] ^= top[j]*C(tot, K-1), tot ++;
                tot = K + i - 1 - 1;
                for(reg int j = K+1; j >= 2; j --)
                        A[1][i] ^= left[j]*C(tot, K+i-2), tot ++;

        }
        for(reg int i = 2; i <= 100; i ++){
                int tot = K - 1;
                for(reg int j = K+i; j >= 2; j --)
                        A[i][1] ^= left[j]*C(tot, K-1), tot ++;
                tot = K + i - 2;
                for(reg int j = K+1; j >= 2; j --)
                        A[i][1] ^= top[j]*C(tot, K+i-2), tot ++;
        }
        for(reg int i = 2; i <= 100; i ++)
                for(reg int j = 2; j <= 100; j ++) A[i][j] = A[i-1][j] ^ A[i][j-1];
        /* for(reg int i = 2; i <= 100; i ++){ for(reg int j = 2; j <= 100; j ++) printf("%d ", A[i][j]); printf("\n"); } */
        scanf("%d", &Q);
        while(Q --){
                int n, m;
                scanf("%d%d", &n, &m);
                printf("%d\n", A[n][m]);
        }
        return 0;
}