BZOJ 3329 xorequ

题面

不是权限题美滋滋。

x xor 3x=2xx\ xor\ 3x=2xx xor 2x=3xx\ xor\ 2x=3x

x and 2x+x+2x=3xx\ and\ 2x + x + 2x =3x

所以x and 2x=0x\ and\ 2x=0

首先我们考虑f0[x]f0[x]表示有x位二进制数(无限制),其中第x位填0的方案数,(位从1开始到第x位)

f1[x]f1[x]表示有x位二进制数(无限制),其中第x位填1的方案数,

所以f0[x]=f0[x1]+f1[x1]f0[x]=f0[x-1]+f1[x-1]f1[x]=f0[x1]f1[x]=f0[x-1]

对于第一问,我们就可以数位DP了。

对于第二问,我们可以通过矩阵乘法优化DP。

注意考虑边界情况:

  1. 不要忘记去掉0的情况。
  2. 不要忘记n是否可以(2n2^n一定可以,nn不一定)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
Author: CNYALI_LK
LANG: C++
PROG: 3329.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
const ll p=1000000007;
void Add(ll &a,ll b){
a-=((a+=b)>=p?p:0);
}
struct matrix{
ll a[3][3];
ll *operator [](ll n){return a[n];}
matrix operator *(matrix b){
matrix c;
for(ll i=1;i<=2;++i)
for(ll j=1;j<=2;++j){
c[i][j]=0;
for(ll k=1;k<=2;++k)Add(c[i][j],a[i][k]*b[k][j]%p);
}
return c;
}
};
matrix operator ^ (matrix a,ll b){
matrix c;
c[1][1]=c[2][2]=1;
c[1][2]=c[2][1]=0;
while(b){
if(b&1)c=c*a;
a=a*a;
b>>=1;
}
return c;
}
ll f0[88],f1[88];
matrix a,b;
int main(){
#ifdef cnyali_lk
freopen("3329.in","r",stdin);
freopen("3329.out","w",stdout);
#endif
ll t,n;
t=read();
while(t){
n=read();
f0[1]=f1[1]=1;
for(ll i=2;i<=64;++i){
f0[i]=f1[i-1]+f0[i-1];
f1[i]=f0[i-1];
}
ll ans=0;
for(ll i=63;i;--i){
if((1LL<<(i-1))&n){
ans+=f0[i];
if((1LL<<i)&n){
--ans;
break;
}
}
}
printf("%lld\n",ans);
b[1][1]=1;b[2][1]=1;
a[1][1]=a[1][2]=a[2][1]=1;
b=(a^(n-1))*b;
printf("%lld\n",(b[1][1]+b[2][1])%p);
--t;
}
return 0;
}
文章目录
|

博客使用Disqus作为评论系统