题解 P1762 【偶数】

题目一看... 杨辉三角？ %2意义下的面积？ 输出一下看看吧 ``` 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 ``` *这是在每一位都`%2`后只输出`1`后得到的结果* 好好看啊wq 你为什么不试试在这里面找找规律呢？ 我们可以很明显的观察到，每一个三角形都是由下面一个三角形所叠加出来的 ``` 1 11 ``` 每个第$ 2^i $ 行，就是一个三角形的结尾 每个第$ 2^i $ 行，就是由三个第 $ 1 $ 到 $ 2^{i-1} $的三角形组成 看起来第$ 2^i $ 行的结果我们可以算出来: $$ f(1)=1 $$ $$ f(i) = f(i/2)*3 $$ 整理一下: 第 $ 2^i $ 行有 $ 3^{i-1} $ 个`1` 恩，快速幂大法解决就可以 问题在于，不是$2^i$的怎么办？ 恩，先打表找规律吧>_< ``` 1 : 1 1 2 : 1 1 3 3 : 1 1 5 4 : 1 1 1 1 9 5 : 1 1 11 6 : 1 1 1 1 15 7 : 1 1 1 1 19 8 : 1 1 1 1 1 1 1 1 27 9 : 1 1 29 10 : 1 1 1 1 33 11 : 1 1 1 1 37 12 : 1 1 1 1 1 1 1 1 45 13 : 1 1 1 1 49 14 : 1 1 1 1 1 1 1 1 57 15 : 1 1 1 1 1 1 1 1 65 16 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 81 17 : 1 1 83 18 : 1 1 1 1 87 19 : 1 1 1 1 91 20 : 1 1 1 1 1 1 1 1 99 21 : 1 1 1 1 103 22 : 1 1 1 1 1 1 1 1 111 23 : 1 1 1 1 1 1 1 1 119 24 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 135 25 : 1 1 1 1 139 26 : 1 1 1 1 1 1 1 1 147 27 : 1 1 1 1 1 1 1 1 155 28 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 171 29 : 1 1 1 1 1 1 1 1 179 30 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 195 31 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 211 32 : 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 243 ``` 随便推一个吧qwq 14? 首先先找到2的次幂--8 ans+=27 剩下的相当于是 第6层 ×2 以此类推qwq 以下是代码 ```cpp #include <cstdio> #include <cmath> const long long mod=1000003; long long sum,ans,n; inline long long lowbit(long long x){return x&(-x);} inline long long ksm(long long a,long long p){// 标准快速幂 long long res=1,base=a; while(p){ if(p&1) res=(res*base)%mod; base=(base*base)%mod; p>>=1; } return res; } long long dfs(long long now){ long long tmp=lowbit(now);// lowbit 用于快速找到第一个我可以分层的地方 if(tmp==now){ ans=ksm(3,(std::log(now)/std::log(2)));// tmp==now 说明 now 是 2的次幂 （ log 快速求指数) return 2; // 翻倍 } else{ long long tmp1=dfs(now-tmp);// 剪掉算过的 ans=(ans+tmp1*ksm(3,(std::log(tmp)/std::log(2))))%mod; return tmp1*2; } } int main(){ scanf("%lld",&n); dfs(n); if(n%2==0) sum=(((1+n)%mod)*((n/2)%mod))%mod; else sum=((((1+n)/2)%mod)*(n%mod))%mod; // 都说这个地方要乘法逆元之类的高端操作...我就直接暴力了 printf("%lld",((sum-ans)%mod+mod)%mod); } ```