P1762偶数（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 11k | 阅读时长 ≈ 10 分钟

这里有一篇题解。

P1762偶数（题解）

点我

PS.

此题关于杨辉三角，所以应该是数论。
但是像我这种菜鸡，只能暴力打表出奇迹了。
然后突然发现，好像自己打出了最短的题解。

Solution.

首先，对于$\texttt{n}$比较小的数据可以打出一个表。
打表辅助程序如下，相当于$\texttt{O(n}^\texttt{2}\texttt{)}$暴力解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=15;
int a[2][10005],ans[10005],tr[10005];
int main()
{
	memset(a,0,sizeof(a)),tr[0]=tr[1]=0;
	for(int i=0,tot=0;i<=N;i++,tot=0)
	{
		a[i&1][0]=1;
		for(int j=1;j<=i;j++) a[i&1][j]=a[1-(i&1)][j]+a[1-(i&1)][j-1];
		for(int j=0;j<=i;j++) a[i&1][j]&=1;
		for(int j=0;j<=i;j++) tot+=1-(a[i&1][j]&1);
		tr[i]=tr[i/2]+lowbit(i)/2,ans[i]=tot;
		for(int j=0;j<=i;j++) printf("%c%c",a[i&1][j]?'*':'.',j==i?'\n':' ');
//		printf("%d:%d\n",i+1,ans[i]);
	}
	return 0;
}

打出来的表如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
*
* *
* . *
* * * *
* . . . *
* * . . * *
* . * . * . *
* * * * * * * *
* . . . . . . . *
* * . . . . . . * *
* . * . . . . . * . *
* * * * . . . . * * * *
* . . . * . . . * . . . *
* * . . * * . . * * . . * *
* . * . * . * . * . * . * . *
* * * * * * * * * * * * * * * *

然后，发现它是一个分形图形，于是我们考虑用递归求解。
设我们当前要处理的三角形边长为$\texttt{n}$，答案为$\texttt{f(n)}$，那么

于是，这个$\texttt{f(n)}$可以用递归法加上快速幂求解。
当然也可以预处理出所有$\texttt{3}^\texttt{k}$。

Coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll QY=1000003;
inline ll lowbit(ll x) {return x&(-x);}
inline ll upbit(ll x) {for(ll i=1;;i<<=1) if(i>=x) return i/2;return 0;}
inline ll qpow(ll a,ll q) {ll ans=1;for(;q;q>>=1,a=a*a%QY) if(q&1) ans=ans*a%QY;return ans;}
inline ll dfs(ll x)
{
	if(lowbit(x)==x) return qpow(3,(ll)(log(x)/log(2)));
	return (qpow(3,(ll)(log(upbit(x))/log(2)))+2*dfs(x-upbit(x))%QY)%QY;
}
int main()
{
	ll n,sum;
	scanf("%lld",&n),sum=n%2?(n%QY)*((n+1)/2%QY)%QY:(n/2%QY)*((n+1)%QY)%QY;
	printf("%lld\n",((sum-dfs(n))%QY+QY)%QY);
	return 0;
}