打表找规律吼题哇
首先打出\(1-1000\)内的答案的表
0
0
1
1
4
6
9
9
16
...
448363
有个**规律啊qwq
然后想到用\(\frac{n(n+1)}{2}\)(也就是数字的总数)减去答案,得到另一个表
1
3
5
9
11
15
19
27
29
...
好像有点规律啊,,,
发现第\(2^i\)行的数为\(3^i\)
然后前后做差,得到
1
2
2
4
2
4
4
8
2
4
4
8
4
8
8
16
...
发现任取一段\(1-2^i\),然后以\(2^{i-1}\)为界,发现前面一半数每个乘2得到了后面一半数,并且对于前后两半类似的处理下去也是这个结论
于是看一下题解整理一下,我们就能知道答案为
\[\frac{n(n+1)}{2}-\sum_{i=0}^{\lfloor log_2n\rfloor}[n\&2^i]2^o3^i(o\text{为二进制第i位往后的(编号更大)二进制位上1的个数}
)\]
)\]
然后做完了qwq
代码中我从高到低地模拟,所以复杂度好像偏高(雾),但是意思是一样的.所以看不懂直接套用式子吧
#include<algorithm>
#include<iostream>
#include<cstring>
#include<complex>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#define LL long long
#define il inline
#define re register
using namespace std;
const LL mod=1000003;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL n,m,ans,dv=500002; //dv为那个模数意义下2的逆元
il LL cch(LL a,LL b) //快(gui)速乘,防止爆longlong
{
LL an=0;
while(b)
{
if(b&1) an=(an+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return an;
}
int main()
{
m=n=rd();
int d=1;
while(n)
{
LL i=1,c=d;
while((i<<1ll)<=n) c=(c*3)%mod,i<<=1ll; //强行找highbit(滑稽)
ans=(ans+c)%mod;
n-=i;
d<<=1;
}
printf("%lld\n",((cch(m,m+1)*dv)%mod-ans+mod)%mod);
return 0;
}
至于更好理解的代码,请右转此题题解区