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