洛谷 P1762 偶数

时间：2023-03-09 09:29:43
洛谷 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

题解：

#include<cstdio>

#include<iostream>

#define mo 1000003

using namespace std;

long long n,d,z,ans,a[],b[],v,p;

int i,t;

int main(){

    cin>>v;

    n=v;z=;d=z<<;

    t=;

    while(n!=){

        if(n>=d){

            n=n-d;

            a[++a[]]=t;

        }

        d>>=;

        t--;

    }

    b[]=;

    for(int i=;i<=a[];i++)b[i]=(b[i-]*)%mo;

    for(int i=;i<=a[];i++)ans+=b[a[i]]*(long long)(z<<i-);

    p=(((z+v%mo)*(v%mo))/);

    p%=mo;

    ans%=mo;

    if(p<ans)p+=mo;

    p=(p-ans)%mo;

    cout<<p;

    return ;

}

 一世安宁

相关文章