当前位置 : 主页 > 编程语言 > 其它开发 >

题解 洛谷P1762 偶数/6.21校内考试T2

来源:互联网 收集:自由互联 发布时间:2022-06-29
题目传送门 首先,由于题中只需要知道杨辉三角每一项的奇偶性,我们不妨将其前几行列出来 杨辉三角前32行(1代表奇数,0代表偶数): 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1
题目传送门

首先,由于题中只需要知道杨辉三角每一项的奇偶性,我们不妨将其前几行列出来

杨辉三角前32行(1代表奇数,0代表偶数):

1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

通过观察找规律,可以发现

1 0
1 1

是杨辉三角的一个基本单位。

为甚么这样说呢?把一个

1 0
1 1

看作一个1,把一个

0 0
0 0

看作一个0,得到的依然是杨辉三角的排列。

既然这样,如果我们把这个新数列再按一个 2\times 2 的小正方形为0和1来构造第三个数列的话,那么每一个1代表的则是

1
1 1
1 0 1
1 1 1 1

3\times 3 个1。

这样就可以发现,杨辉三角前 2^k 项1的个数是 3^k

然后我们将n进行二进制拆分,如例:

n=21时

1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1

拆分后可得 n=2^4+2^2+2^0 ,由于一次拆分后剩下的可以被割成两部分:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0     1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1

当中奇数个数完全相同。

同理,第二次拆分就可以分成 2\times 2 部分,第m次拆分就可以分成m部分。

于是我们设n拆分得到的集合为a,并升序排列,并设 |a|=b 为了方便计算,先将 a_i(i\in[1,b]) 中的每一个元素变成 \log_2a_i

可得:杨辉三角前n行奇数个数为 \sum\limits_{i=1}^b3^{a_i}\times 2^i

加以快速幂,时间复杂度 \Theta(log^2n)

记得开long long及取模

CODE
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mn=1e2+10;
const int mm=1e2+10;
const ll mod=1e6+3;
const int inf=0x3f3f3f3f;
const int fni=0xc0c0c0c0;
ll a[mn],cnt,n;
int b[mn];
inline void read_init(){
   ll nn=n=read<ll>();
   while(nn){
       a[++cnt]=nn&-nn;
       nn-=nn&-nn;
  }
   for(int i=1;i<=cnt;i++){
       while(a[i]){
           a[i]>>=1;
           b[i]++;
      }
       b[i]--;
  }
}
inline ll qpow(ll a,ll b){
   ll ans=1;
   while(b){
       if(b&1)
           ans=ans*a%mod;
       b>>=1;
       a=a*a%mod;
  }
   return ans;
}
int main(){
   read_init();
   ll sum=0;
   for(int i=cnt;i>=1;i--)
       sum=(sum+((1<<(cnt-i))%mod)*qpow(3,b[i]))%mod;
   ll o=((n%mod)*((n+1)%mod)>>1)%mod;
   write((((o-sum)%mod)+mod)%mod,1);
   return 0;
}


网友评论