Description
click me
Solution
发现
x⊕3x=2x
x
⊕
3
x
=
2
x
即
x⊕2x=3x
x
⊕
2
x
=
3
x
，考虑异或是不进位的加法，题目条件等价于
x
x
的二进制表示中不存在连续的11。 第一问数位dp，第二问直接矩乘优化dp即可。
Source
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<
int,
int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <
typename T>
inline bool chkmax(T &a, T b) {
return a < b ? a = b,
1 :
0; }
template <
typename T>
inline bool chkmin(T &a, T b) {
return b < a ? a = b,
1 :
0; }
inline int read()
{
register int _, __;
register char c_;
for (_ =
0, __ =
1, c_ = getchar(); c_ <
'0' || c_ >
'9'; c_ = getchar())
if (c_ ==
'-') __ = -
1;
for ( ; c_ >=
'0' && c_ <=
'9'; c_ = getchar()) _ = (_ <<
1) + (_ <<
3) + (c_ ^
48);
return _ * __;
}
inline void File()
{
#ifdef hany01
freopen(
"bzoj3329.in",
"r", stdin);
freopen(
"bzoj3329.out",
"w", stdout);
#endif
}
LL dp[
110][
2];
int cnt, a[
110];
inline void Init()
{
dp[
0][
0] =
1;
For(i,
1,
100)
dp[i][
0] = dp[i -
1][
0] + dp[i -
1][
1], dp[i][
1] = dp[i -
1][
0];
}
inline LL dfs(
int pos,
int pre,
int lmt)
{
if (!pos)
return 1;
if (!lmt)
return dp[pos +
1][pre];
register LL tmp =
0;
For(i,
0, lmt ? a[pos] :
1)
if (!pre || !i) tmp += dfs(pos -
1, i, lmt && i == a[pos]);
return tmp;
}
inline LL Solve1(LL n)
{
cnt =
0;
while (n) a[++ cnt] = n %
2, n /=
2;
return dfs(cnt,
0,
1);
}
struct Matrix
{
int ret[
2][
2], x, y;
Matrix(
int a) {
Set(ret,
0);
if (a ==
1) ret[
0][
0] = ret[
1][
1] =
1;
x = y =
2;
}
};
Matrix
operator * (Matrix A, Matrix B) {
Matrix C(
0);
rep(i, A.x) rep(j, B.y) rep(k, A.y)
(C.ret[i][j] += A.ret[i][k] *
1ll * B.ret[k][j] % Mod) %= Mod;
return C;
}
Matrix
operator ^ (Matrix a, LL b) {
Matrix Ans(
1);
for ( ; b; b >>=
1, a = a * a)
if (b &
1) Ans = Ans * a;
return Ans;
}
inline int Solve2(LL n)
{
Matrix A(
0), B(
0);
A.ret[
0][
0] =
1, A.ret[
0][
1] =
0, A.ret[
1][
0] =
1, A.ret[
1][
1] =
1,
B.ret[
0][
0] =
1, B.ret[
0][
1] =
1, B.ret[
1][
0] =
1, B.ret[
1][
1] =
0;
B = B ^ (n -
1), A = A * B;
return (A.ret[
1][
1] + A.ret[
1][
0]) % Mod;
}
int main()
{
File();
Init();
register LL n;
for (
register int T = read(); T --; ) {
scanf(
"%lld", &n);
printf(
"%lld\n%d\n", Solve1(n) -
1, Solve2(n));
}
return 0;
}
