洛谷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

 

 https://www.luogu.org/problemnew/solution/P1762 Orz

// luogu-judger-enable-o2
#include<cstdio>
#define int long long 
const int mod = 1000003;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
int B[62], N;
int fastpow(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
main() {
    N = read();
    int tot = (N % mod) * ((N % mod) + 1) / 2, now = 1;
    for(int i = 61; i >= 0; i--)
        if(N & (1ll << i)) //判断第i位是否存在 
            tot = (tot - fastpow(3, i) * now % mod + mod) % mod, now = (now % mod * 2) % mod;
    printf("%lld", tot % mod); 
}