P1762 偶数&杨辉三角(天立OI)

解题思路

一.结论法

杨辉三角形结论

1. 第\(n\)行有\(n\)个数。

2. 每行奇数个数必为\(2^k\)（\(k\)不是行数）

3. 当行数恰为\(2^k\)时，奇数个数为\(2^k\)个，无偶数。

4. 当行数恰为\(2^k\)时，其前\(2^k\)行有\(3^{(k-1)}\)个奇数。

5. 前\(n\)行奇数个数（\(p\)）：

   \[\notag n=2^{k1}\times 2^{k2}\times 2^{k3}....\times 2^{kn}\\ p=1\times 3^{kn}+2\times 3^{kn-1}+2^2\times 3^{kn-2}+....+2^{n-1}\times 2^{k1} \]

6. 前\(n\)行偶数个数$(n-1)\times n /2 -p $

二.分析法

既然看不出来，那就打表（\(\bmod 2\)）：

1  1
2  1 1
3  1 0 1
4  1 1 1 1
5  1 0 0 0 1
6  1 1 0 0 1 1
7  1 0 1 0 1 0 1
8  1 1 1 1 1 1 1 1           *****
9  1 0 0 0 0 0 0 0 1
10 1 1 0 0 0 0 0 0 1 1
11 1 0 1 0 0 0 0 0 1 0 1
12 1 1 1 1 0 0 0 0 1 1 1 1   *****
13 1 0 0 0 1 0 0 0 1 0 0 0 1
14 1 1 0 0 1 1 0 0 1 1 0 0 1 1
15 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

这个就有规律了：

1. 当\(n=2^k\)时，前面一共有\(3^k\)个\(1\)

2. 当\(n!=2^k\)时，可以将\(n\)拆成\(n=2^{k1}\times 2^{k2}\times 2^{k3}....\times 2^{kn}\)

   但这个又有什么用呢？不妨举个例子：

   \[\notag n=12=2^3+2^2\\ 前n行奇数个数p\\ p=3^3+2*3^2\\ 看图（上面） \]

可以发现方法一里面的规律：

综上，下次遇见关于杨辉三角的题先打表！！

CODE

#include
#define ll __int128
using namespace std;
const ll maxn = 300;
ll int_maxn=1e9;
ll ll_maxn=1e18;
inline ll read_int(){
    ll a=0,f=0,g=getchar();
    while(g<'0'||g>'9'){if(g=='-') f=1;g=getchar();}
    while('0'<=g&&g<='9') a=a*10+g-'0',g=getchar();
    return f ? -a : a;
}
inline void write(ll s,bool f){
    ll top=0,a[40];
    if(s<0) s=-s,putchar('-');
    while(s) a[++top]=s%10,s/=10;
    if(top==0) a[++top]=0;
    while(top) putchar(a[top]+'0'),top--;
    if(f) putchar('\n');
}
ll n;

ll top=0,jz[10000],mod=1000003;
inline void er(){
	ll m=n;
	for(ll i=0;m;i++){
		if(m&1) jz[++top]=i;
		m>>=1;
	}
}

inline ll qpow(ll n,ll c){
	ll ans=1;
	while(c){
		if(c&1) ans=ans*n%mod;
		n=n*n%mod,c>>=1;
	}
	return ans;
}

inline void read(){
	n=read_int();
	er();
	ll a=1;
	ll ans=0;
	for(ll i=top;i>=1;i--){
		ans=ans+a*qpow(3,jz[i])%mod;
		a=a*2%mod;
		ans%=mod;
	}
	ll L=(n+1)%2 ? n/2%mod*(n+1)%mod : (n+1)/2%mod*(n)%mod;
	ans=L-ans;
	write(ans<0 ? ans+mod : ans,1);
}

int main (){
	read();
}

THE END