自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:28:48，当前版本为作者最后更新于2013-10-07 22:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

打出杨辉三角形前若干行的奇偶分布情况，便会发现这是一个分形图形。这样就可以用递归解决问题。具体实现时可以直接计算，也可以先算总个数再减去奇数的数量（比较好算）。用扩展欧几里德或欧拉定理来解决除法取模问题，或是直接用高精计算，最后取模。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
long long n,i,f[200],j,t,s;
long long p=1000003,l,k,pp;
long long aa(long long n)
{
     long long i=2LL,j=1LL,q;
     if (n<=2) return 0;
     while (i*2<=n){i=i*2;j++;}
     return (2*aa(n-i)%p+f[j+1]-2*f[j]%p-((i*2-n)%p)*((i*2-n-1)%p)*l+p*p*p)%p;
}
int main()
{
    cin>>n;f[1]=0;i=2;j=1;
    k=2;l=1;pp=p-2;
    while (pp>0)
    {
          if (pp%2==1) l=l*k%p;
          k=k*k%p;pp=pp/2;
    }   
    while (i<=n)
    {
          j++;s=i%p;t=s*(s-1)%p;
          f[j]=((f[j-1]*3%p)+((i%p)*((i-1)%p)%p)*l)%p;
          i=i*2;
    }
    cout<<aa(n);
    system("pause");
    return 0;
}