luogu P1762 偶数

打表找规律吼题哇

首先打出\(1-1000\)内的答案的表

有个**规律啊qwq

然后想到用\(\frac{n(n+1)}{2}\)(也就是数字的总数)减去答案,得到另一个表

好像有点规律啊,,,

发现第\(2^i\)行的数为\(3^i\)

然后前后做差,得到

发现任取一段\(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;

}

至于更好理解的代码,请右转此题题解区

巴特西

luogu P1762 偶数

最新文章

热门文章