题目大意

求杨辉三角形前 $n$ 行的偶数个数，对 $1000003$ 取模。

分析

对杨辉三角奇数打表。

1
1 1
1   1
1 1 1 1
1	   1
1 1	 1 1
1   1   1   1
1 1 1 1 1 1 1 1
1			   1
1 1			 1 1
1   1		   1   1
1 1 1 1		 1 1 1 1
1	   1	   1	   1
1 1	 1 1	 1 1	 1 1
1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1							   1
1 1							 1 1
1   1						   1   1
1 1 1 1						 1 1 1 1
1	   1					   1	   1
1 1	 1 1					 1 1	 1 1
1   1   1   1				   1   1   1   1
1 1 1 1 1 1 1 1				 1 1 1 1 1 1 1 1
1			   1			   1			   1
1 1			 1 1			 1 1			 1 1
1   1		   1   1		   1   1		   1   1
1 1 1 1		 1 1 1 1		 1 1 1 1		 1 1 1 1
1	   1	   1	   1	   1	   1	   1	   1
1 1	 1 1	 1 1	 1 1	 1 1	 1 1	 1 1	 1 1
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

于是递推公式

$$ f(2^t+n) = f(2^t) + 2f(n) $$

就是显然的了，那么偶数即是全部的减去奇数个数。

const ll MOD = 1000003;
ll nn[10086];

#define ACM_MOD MOD

#include "template/basic/qpow.hpp"
#include "template/basic/inv.hpp"

int main() {
	ll n = rr();
	nn[1] = 1;
	for (ll i = 2; i <= 100; i++)
		nn[i] = nn[i - 1] * 3 % MOD;
	ll t = 1, ans = 0;
	for (ll i = 1; i <= 100; i++) {
		if ((t & n) > 0)
			ans = (ans * 2 + nn[i]) % MOD;
		t = t << 1;
		if (t > n)
			break;
	}
	n = n % MOD;
	ll sum = n * (n + 1) % MOD * inv(2) % MOD;
	printf("%lld\n", (sum - ans + MOD) % MOD);
	return 0;
}