关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年10月26日
玄学数学 — Luogu P1762 偶数

0x01 写在之前

题目链接: [https://www.luogu.org/problemnew/show/P1762]

这道题形象生动的说明了从几何层面来找规律是多么的方便

~~打表找规律是多么的我方便~~

0x02 题目

题目一看…

杨辉三角?

%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

以下是代码

#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);
}
算竞

textsms