洛谷P1762 偶数

P1762 偶数

题目描述

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

输入输出格式

输入格式：

一个数

输出格式：

结果

输入输出样例

输入样例#1： 复制

6

输出样例#1： 复制

6

说明

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

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

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

杨辉三角形的前七行：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

题解里的dalao已经说得very清楚了，大家可以去看看https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1762

#include<cstdio>
#include<iostream>
#define mo 1000003
using namespace std;
long long n,d,z,ans,a[55],b[55],v,p;
int i,t;
int main(){
    cin>>v;
    n=v;z=1;d=z<<50;
    t=50;
    while(n!=0){
        if(n>=d){
            n=n-d;
            a[++a[0]]=t;
        }
        d>>=1;
        t--;
    }
    b[0]=1;
    for(int i=1;i<=a[1];i++)b[i]=(b[i-1]*3)%mo;
    for(int i=1;i<=a[0];i++)ans+=b[a[i]]*(long long)(z<<i-1);
    p=(((z+v%mo)*(v%mo))/2);
    p%=mo;
    ans%=mo;
    if(p<ans)p+=mo;
    p=(p-ans)%mo;
    cout<<p;
    return 0;
}