JOHNKRAM 最近在研究集合。他从 $[1,2n]$ 中任选了 $n$ 个不同的整数，组成了 $inom{2n}{n} $ 个不同的集合。现在他想知道，在这些集合中，有多少个集合含有偶数个偶数？答案可能很大，你只需要告诉他答案 $ ext{mod} 1000003$ 的结果即可。
$nle 10^{18}$ 。
题解
结论题+Lucas定理
结论：
1. 当 $n$ 为奇数时，答案为 $frac{inom{2n}{n}}2$ ；
2. 当 $n$ 为偶数且为 $4$ 的倍数时，答案为 $frac{inom{2n}{n}+inom{n}{frac n2}}2$ ；
3. 当 $n$ 为偶数且不为 $4$ 的倍数时，答案为 $frac{inom{2n}{n}-inom{n}{frac n2}}2$ ；
我不会证明...打表打出来的...
然后使用Lucas定理求组合数即可。
另外本题好像还可以用数位dp来做。
#include <cstdio>
#define mod 1000003
#define inv2 500002
typedef long long ll;
ll fac[mod] , inv[mod] , fin[mod];
ll C(ll n , ll m)
{
if(n < m) return 0;
else if(n <= mod) return fac[n] * fin[m] % mod * fin[n - m] % mod;
else return C(n / mod , m / mod) * C(n % mod , m % mod) % mod;
}
int main()
{
ll n;
int i;
fac[0] = fac[1] = inv[1] = fin[0] = fin[1] = 1;
for(i = 2 ; i < mod ; i ++ )
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fin[i] = fin[i - 1] * inv[i] % mod;
}
scanf("%lld" , &n);
if(n & 1) printf("%lld
" , C(2 * n , n) * inv2 % mod);
else if(n & 2) printf("%lld
" , (C(2 * n , n) - C(n , n / 2) + mod) * inv2 % mod);
else printf("%lld
" , (C(2 * n , n) + C(n , n / 2)) * inv2 % mod);
return 0;
}