洛谷P1762 偶数(找规律)

2018-07-13 02:36:51来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

给定一个正整数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); 
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

下一篇:BZOJ1050: [HAOI2006]旅行comf(并查集 最小生成树)