[数据结构与算法] #664.数列思维

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> #664.数列思维 -> 正文阅读

[数据结构与算法]#664.数列思维

link
位运算思维 middle

题意

在这里插入图片描述

思路

注意到 $c$ 数列是单调递增的，而 $c_i = c_{i-1} \ xor\ a_i$ ，由xor的性质， $c_{i-1}$ 二进制下的位数一定小于 $a_i$ （因为比如1000 xor 1011 = 0011小于1000）
也就是说， $a_1,a_2,a_3...$ 每个数的位数不能相同，即 [1], [2, 3], [4, 5, 6, 7], […] 每个集合中最多取一个数。
例如 $d = 5$ 时， [1], [2, 3], [4, 5]，方案为 2 * 3 * 3 - 1 = 17种

代码

int d, m;
void solve() {
    cin >> d >> m;
    int ans = 1;
    int tmp = d;
    vector<int> v;
    for(int i = 1; i <= tmp; i <<= 1) {
        v.push_back(i+1);
        tmp -= i;
    }
    if(tmp) v.push_back(tmp + 1);
    for(int i = 0; i < v.size(); i++) {
    	ans = ans * v[i] % m;
    }
    if(!ans) ans = m - 1;
    else ans--;
    cout << ans << endl;
}