BZOJ3329: Xorequ(二进制数位dp 矩阵快速幂)
2024-09-05 18:16:11
题意
Sol
挺套路的一道题
首先把式子移一下项
\(x \oplus 2x = 3x\)
有一件显然的事情:\(a \oplus b \leqslant c\)
又因为\(a \oplus b + 2(a \& b) = c\)
那么\(x \& 2x = 0\)
也就是说,\(x\)的二进制表示下不能有相邻位
第一问直接数位dp即可
第二问比较interesting,设\(f[i]\)表示二进制为\(i\)的方案数,转移时考虑上一位选不选
如果能选,方案数为\(f[i - 2]\)
不选的方案数为\(f[i - 1]\)
#include<bits/stdc++.h>
#define LL long long
//#define int long long
#define file {freopen("a.in", "r", stdin); freopen("a.out", "w", stdout);}
using namespace std;
const int MAXN = 233, mod = 1e9 + 7;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL N;
struct Matrix {
int m[3][3];
Matrix() {
memset(m, 0, sizeof(m));
}
Matrix operator * (const Matrix &rhs) const {
Matrix ans;
for(int k = 1; k <= 2; k++)
for(int i = 1; i <= 2; i++)
for(int j = 1; j <= 2; j++)
(ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;
return ans;
}
};
Matrix MatrixPow(Matrix a, LL p) {
Matrix base;
for(int i = 1; i <= 2; i++) base.m[i][i] = 1;
while(p) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
LL num[MAXN], tot; LL f[MAXN][2];
LL dfs(int x, bool lim, bool pre) {
if(!lim && (~f[x][pre])) return f[x][pre];
if(x == 0) return 1;
LL ans = 0;
if(!pre && (num[x] == 1 || (!lim))) ans += dfs(x - 1, lim, 1);
ans += dfs(x - 1, lim && num[x] == 0, 0);
if(!lim) f[x][pre] = ans;
return ans;
}
LL dp(LL x) {
tot = 0;
while(x) num[++tot] = x & 1, x >>= 1;
return dfs(tot, 1, 0);
}
main() {
// file;
memset(f, -1, sizeof(f));
int T = read();
while(T--) {
N = read();
printf("%lld\n", dp(N) - 1);
Matrix a;
a.m[1][1] = 1; a.m[1][2] = 1;
a.m[2][1] = 1; a.m[2][2] = 0;
a = MatrixPow(a, N);
printf("%d\n", (a.m[1][1] + a.m[1][2]) % mod);
}
return 0;
}
/*
1
5
*/
最新文章
- redis中setbit的用法
- iOS 自定义图片和文字垂直显示按钮<;上面是图片,文字显示下面>;
- android中paint的setXfermode属性
- MVC部分视图(Partial View)
- How To Set Up vsftpd on CentOS 6
- [shell基础]——cut命令
- iOS 虚拟机测试出现的相关问题
- C++11 能好怎?
- Java读书笔记二(封装类)
- 我的python学习笔记一
- 面向对象编程总结--Python
- uva1471 二叉搜索树
- Java基础练习2(构造方法)
- xxl-job入门实践
- F#周报2019年第13期
- quill富文本编辑器 API
- HTML 5 Web 本地存储
- spring 文件加载 通过listener的类获取配置文件 并加载到spring容器中
- [原创]HTML 用div模拟select下拉框
- 使用 IntraWeb (25) - 基本控件之 TIWRegion
热门文章
- CF1101B Accordion 模拟
- 2-32 while
- Codeforces-Salem and Sticks(枚举+思维)
- p标签text-align:justify以及CSS文字两端对齐
- python3 关键字和可变参数笔记
- 事务背书 ACID, CAP, BASE
- Python报错:UnicodeEncodeError &#39;gbk&#39; codec can&#39;t encode character
- 转 Python 操作 MySQL 数据库
- Silverlight 鼠标双击 事件
- Unity 用JSON库序列化与反序列化类,字典