XOR Matrix 组合数学

XOR Matrix
题意，给出n个数，交替运算m-1次，求出最后结果，o运算法则为a[1][x] = a[0][x]^a[0][x+1](x 从1~n)
题解地址
需要注册账号才能看，题解中讲解的十分详细，首先利用一项一项合并发现第x行都可以化成只与第一行有关系，通过找规律可以发现第1行的元素项出现正好次组合数c(i,n)，根据异或运算的性质x^x = 0,将杨辉三角对2取模后,可得最后运算规律中2^i项正好可以化简成两项,所以正好利用二进制的性质可以把任意m-1次的运算给表示出来。这样只需要把（m-1）的二进制中 位数为1的那一项计算出来就行了，相当于对m取log,所以最后的复杂度是o(n*logm)
注意这是一个卷积运算，题解中找规律时就是利用开头的o运算法则找的规律，最后得到的也是运算法则o的简化版本，但是还是需要进行o(n)的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long long a[2][100005];
long long m;
int main()
{
    int n;
    cin>>n>>m;
    m--;
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[0][i]);
    int x = 1,y = 0;
    long long st;
    while(m)
    {
        swap(x,y);
//        只开两维交替运算
//        for(int i=60;i>=0;i--)
//        {
//            if(m>=((long long)1<<i))
//            {
//                st = ((long long )1<<i);
//                break;
//            }
//        }
//        m-=st;    //手写计算二进制中1的位置
      cout<<m<<endl;
       long long k  =__builtin_ctzll(m);
       //返回右起第一个数字1的后面0的个数
       cout<<k<<"*"<<endl;
        for(int i=1; i<=n; i++)
        {
                a[y][i] = a[x][i]^a[x][(i+(1LL<<k)-1)%n+1];
                //小技巧，避免出现访问a[x][0]
        }
       m-=(1LL<<k);
    }
    int top = 1;
    for(int i=1; i<=n; i++)
    {
        if(top)top = 0;
        else printf(" ");
        printf("%d",a[y][i]);
    }

    return 0;
}

下面是一篇很有用的有关二进制操作的博客
二进制操作

— Built-in Function: int __builtin_ffs (unsigned int x)

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
返回右起第一个‘1’的位置。

— Built-in Function: int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
返回左起第一个‘1’之前0的个数。

— Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
返回右起第一个‘1’之后的0的个数。

— Built-in Function: int __builtin_popcount (unsigned int x)

Returns the number of 1-bits in x.
返回‘1’的个数。

— Built-in Function: int __builtin_parity (unsigned int x)

Returns the parity of x, i.e. the number of 1-bits in x modulo 2.
返回‘1’的个数的奇偶性。

— Built-in Function: int __builtin_ffsl (unsigned long)

Similar to __builtin_ffs, except the argument type is unsigned long.

— Built-in Function: int __builtin_clzl (unsigned long)

Similar to __builtin_clz, except the argument type is unsigned long.

— Built-in Function: int __builtin_ctzl (unsigned long)

Similar to __builtin_ctz, except the argument type is unsigned long.

— Built-in Function: int __builtin_popcountl (unsigned long)

Similar to __builtin_popcount, except the argument type is unsigned long.

— Built-in Function: int __builtin_parityl (unsigned long)

Similar to __builtin_parity, except the argument type is unsigned long.

— Built-in Function: int __builtin_ffsll (unsigned long long)

Similar to __builtin_ffs, except the argument type is unsigned long long.

— Built-in Function: int __builtin_clzll (unsigned long long)

Similar to __builtin_clz, except the argument type is unsigned long long.

— Built-in Function: int __builtin_ctzll (unsigned long long)

Similar to __builtin_ctz, except the argument type is unsigned long long.

— Built-in Function: int __builtin_popcountll (unsigned long long)

Similar to __builtin_popcount, except the argument type is unsigned long long.

— Built-in Function: int __builtin_parityll (unsigned long long)

Similar to __builtin_parity, except the argument type is unsigned long long.

最后

以上就是畅快花瓣最近收集整理的关于XOR Matrix 组合数学的全部内容，更多相关XOR内容请搜索靠谱客的其他文章。