偶数

题目描述

给定一个正整数n，请输出杨辉三角形前n行的偶数个数对1000003取模后的结果。

输入输出格式

输入格式：

一个数

输出格式：

结果

输入输出样例

输入样例#1：

输出样例#1：

说明

对于30%的数据，n<=4000

对于70%的数据，n<=4*10^9

对于100%的数据，n<=10^15

题解：

正如这题所示，数据在n<=10^15的范围内则引导我们去寻找空间更节省，速率更高效的算法。

首先，很明显，杨辉三角之特点在于其行数即等于每行的数字数。因此，可以很容易使用求和公式求出1到n行一共有多少个数字。

其次，通过观察，可以发现，奇数个数比偶数个数更有规律，其规律在于：

每行奇数个数一定为2^k（k为自然数）

当行数恰为2^k（k为自然数）时，奇数个数为2^k，偶数个数为零

当行数恰为2^k（k为自然数）时，奇数个数和恰为3^(k-1)

更巧妙的是：这个规律能更加扩展到一个不为2^k的数上，因为每一个数，都能分解为若干项2^k的和的形式。

举个例子吧：当n=2333;

2333= 2048+256+16+8+4+1

通过暴力程序，我们可以找出2333的所有奇数个数为190985

那么，我们找出如下数字

行数所有奇数个数

2048 177147

256 6561

16 81

8 27 4 9 1 1

我们可以巧妙发现：177147 + 6561*2 + 81*4 + 27*8 + 9*16 + 1*32恰好等于190985！

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 long long k,t,n,ans,nx,mi3[1001],d,mod=1000003,a[1001],p;
 5 int main()
 6 {long long i;
 7 //freopen("11.in","r",stdin);
 8     scanf("%lld",&n);
 9     nx=n;
10      k=0;
11     d=1;
12     for (i=1;i<=51;i++)
13     d*=2;
14      t=51;
15     while (n)
16     {
17         if (n>=d)
18         {
19             n=n-d;
20             a[++k]=t;    
21         }
22         d/=2;
23         t--;
24     }
25     n=nx;
26     mi3[0]=1;
27     for (i=1;i<=a[1];++i)
28      {
29         mi3[i]=(mi3[i-1]*3)%mod;
30      }
31   
32   for (i=1;i<=k;++i)
33      ans=(ans+mi3[a[i]]*(long long)(1<<(i-1)))%mod;
34     //cout<<ans<<endl;
35     ans%=mod;
36      p=(((n%mod)*(n%mod+1)))/2;
37     p%=mod;
38     if (p<ans)p+=mod;
39     p=(p-ans)%mod;
40 printf("%lld
",p);
41 }