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

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

杨辉三角前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及取模

#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;
}