标签：数论

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);
}

]]>

比赛链接:[https://www.luogu.org/contestnew/show/8609]

0x-1

---

首先十分感谢 StudyingFater 大佬出的这场比赛让我们感受到这场数学的魅力(大雾 不过这个抄袭省选题目真的就有点….

0x00 奇怪的支付方式

---

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

题目一看，仿佛回到了小学题目的噩梦，然而作为一位正经Oier,尝试法可不是我们应该做的，仔细一看，发现这个操作似乎有点面熟，我们来把问题抽象一下

有一个整数\(n\)最少有几个数，确保中间任意两个数相加后得到值的集合为[1,n]

是不是有点眼熟？没错，这就在 初学DP(4) – 多重背包及其优化 – Codevs 3269 中的二进制优化法

     1
  10
100

看看上面这一串的数字是不是选择任意两个数加起来都可以得到(100)2以内的任何数？ 由此可得，这道题目的答案就是n的二进制位数+1 当然快速求位数也很简单–\(log_2(n)\) 程序:

#include <cstdio>
#include <cmath>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%d",(int)log2(n)+1);
}

惊不惊喜？意不意外？

0x01 我爱打飞盘

---

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

首先，作为一名乌市一中Oier，打飞盘是一项必备技能 读题!!!看到余数这个东西，第一个想到的就是同余定理 其次，对于数据范围搜索显然是会TLE的，我们就要另辟蹊径了 综合以上两个条件，很容易想到DP的思想，首先定义函数\(f(i,j)\) 其中\(i\)表示第\(i\)个数字，\(j\)表示以这个数字为结尾的数列余数为\(j\)有几种情况 很容易得到下面的代码:

#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,a[2100];
int dp[2100][2100];
int cnt;
inline int max(int a,int b) {return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);dp[i][a[i]%f]++;}// 自己的情况先加上
    for(int i=1;i<=n;i++){
        g=a[i]%f;// 当前数对于f的余数
        for(int j=1;j<i;j++){// 遍历以前的情况
            for(int k=0;k<f;k++){// 遍历余数的情况
                h=(g+k)%f;  // 当前的余数
                dp[i][h]+=dp[j][k];// 累加
            }
        }
    }
    for(int i=1;i<=n;i++) cnt+=dp[i][0];// 统计余数为0的情况
    printf("%d",cnt);// 输出
}

但是时间复杂度呢?\(O(n^2f)\)显然这个数据范围承受起来有点费劲，我们要想办法优化 观察代码发现，我们每次都是就之前的状况累加，也就是说我们没有必要对之前的情况进行遍历，只需要记住累加和就行了，但是余数这个东西比较麻烦的在于，你如何确保不被累加运算? 滚动数组解决一切 不过是不是忘记了什么??? 取模啊!!! 所以正确的代码如下:

#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,l,a[2100],m=1e8;
int dp[2100],dp2[2100];
int cnt;
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        g=a[i]%f;
        for(int k=0;k<f;k++){
            h=(g+k)%f;
            dp[h]+=dp2[k];
            dp[h]%=m;
        }
        for(int k=0;k<f;k++) {dp2[k]+=dp[k];dp2[k]%=m;dp[k]=0;}
        dp2[g]++;// 做到自己在把自己加上防止累加
    }
    printf("%d",dp2[0]);
}

0x02 硬币游戏

---

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

如果不是因为我有事情走的早的话我这题也能A 这题一眼看过去?博弈论？算了怎么高端的东西不好推，我们想想别的 显然，无论怎么操作，最后的结果一定是(int)n/m个m与n%m这样几堆硬币 所以我们计算总共可能的移动次数，对2取模即可得到结果 代码如下:

#include <cstdio>
#include <cmath>
using namespace std;
int T,n,m;
int temp,temp2;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        temp=n/m*(m-1);// 正确的操作应该是temp=n/m*m; temp-=m;合并了一下
        temp2=n%m;
        if(temp2>0) temp2--;// 有可能n%m==0
        if((temp2+temp)%2==0) printf("1\n");
        else printf("0\n");
    }
}

INFxINF END

]]>

排列组合

加法/乘法原理

---

加法原理是分类，乘法原理讲究分步

加法原理

有一个问题，它有 \(n\) 类解决办法，对于第 \(a\) 类解决办法，有 \(x_a\) 种方法完成 那么，总解决方法数就是: $x_1+x_2+x_3+\cdots+x_{n-1}+x_n$

乘法原理

有一个问题，它有 \(n\) 个步骤，对于第 \(a\) 个步骤，有 \(x_a\) 种方法完成 那么，总解决方法数就是: $x_1*x_2*x_3*\cdots*x_{n-1}*x_n$ 这两个规律是显而易见的，甚至被放到了小学奥数里…

排列组合

---

先亮公式 排列: $$A_n^m={{n!} \over {(n-m)!}}$$ 组合: $$C_n^m={{n!} \over {m!(n-m)!}}$$ P.S.: 组合一作 \(P_n^m\) 这是一种较老的表示方法，本博客中使用 \(c_n^m\) 特别定义: $0!=1$ 我相信你的内心一定是迷茫的，让我们来看看这两个东西定义与使用

排列

定义: 从 \(n\) 个数中任意取出 \(m\) 个数，求有多少种方法，不同顺序算作另一种

那么这种问题第一下就会想到乘法原理 对于第一位数， 有 \(n\) 种选法，对于第 2 位数， 有 \(n-1\) 种选法，对于第3位数， 有 \(n-3\) 种选法，对于第 \(y\) 位数， 有 \(n-(y-1)\) 种选法 根据乘法原理得$A_n^m=n*(n-1)*(n-2)*(n-3)*\cdots*(n-m)$ 即$A_n^m={{n!} \over {(n-m)!}}$

组合

定义: 从 \(n\) 个数中任意取出 \(m\) 个数，求有多少种方法，不同顺序算同一种

这个的区别在于不同的顺序在于同一组，不过这么相似，显然是通过上面的推得 也就是说我们要将 $A_n^m$ 中去重，那么我们就要考虑，从 \(m\) 个数中取出的长度为\(m\)的序列会有多少组不同的组合，由排列得 $A_m^m=m!$ $\therefore C_n^m={{n!} \over {m!(n-m)!}}$

组合的特别性质

第一个: $$C_n^m=C_n^(n-m)$$ 证明:$$\because C_n^{n-m}={n! \over {(n-m)![n-(n-m)]!}}={n! \over {(n-m)!n!}}$$ $$\because {C_n^m=n! \over {m!(n-m)!}}$$ $$\therefore {C_n^m=C_n^{n-m}}$$ 第二个: $$ C_n^m=C_{n-1}^m+C_{n-1}^{m-1} $$ 证明:$$ C_{n-1}^m+C_{n-1}^{m-1}={{(n-1)! \over {m!(n-m-1)!}} + {(n-1)! \over {(m-1)!(n-m)!}}} $$ $$={(n-1)(n-2)(n-3) \cdots m \over (n-m)!}+{(n-1)(n-2)(n-3) \cdots (m+1) \over (n-m-1)!}$$ $$={(n-1)(n-2)(n-3) \cdots (m+1)(n-m+m) \over (n-m)!}$$ $$={n! \over {m!(n-m)!}}$$ 这个实际上就是杨辉三角啦 第三个: $$C_n^0+C_n^1+C_n^2+\cdots+C_n^{n-1}+C_n^n=2^n$$ 这个的证明，再用等式的性质…..你们的博主还没有这么厉害… 实际上就是说，你想象一下对 \(n\) 个物品中随意取(1,n)个，这不就相当于你在你在 \(n\) 个物品中间，随意取几个吗 有点眼熟啊…这不是01背包思想吗!! 把每个物品当作一个 0/1 数值，选为 1 不选为 0 ，你么根据乘法原理，总共有 \(2\^n\) 种可能

P2282 组合数问题

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

题目第一眼过去想让人暴力套公式计算,但是…\(t<10^4+1\) 这个速度就比较温暖人心了,有没有什么快速解决的办法的呢? 当然有!杨辉三角了解一下 当然我们不能每个数组数据都处理一波,\(n<2000+1\),后面前缀和保留每一行,后面遍历行数前缀相加就可以了 千万不要忘记边做边取模

代码

---

#include <cstdio>
using namespace std;
long long t,k;
long long n,m;
long long c[2200][2200];
//   n     m
long long cnt=0;
long long sum[2200][2200];
inline long long min(long long a,long long b){return a<b?a:b;}
int main(){
    scanf("%lld%lld",&t,&k);
    for(int i=0;i<=2100;i++){//预处理
        if(i==0){
            for(int j=0;j<=i;j++){
                c[0][j]=1;
                if(c[0][j]%k==0) sum[0][j]=1;// 前缀和
                else sum[0][j]=0;
            }
        }
        else for(int j=0;j<=i;j++){
            if(j==0||j==i) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; // 记得取模
            if(j==0){
                if(c[i][j]%k==0) sum[i][j]=1;
                else sum[i][j]=0;
            }
            else {
                if(c[i][j]%k==0) sum[i][j]=sum[i][j-1]+1;
                else sum[i][j]=sum[i][j-1];
            }
        }
    }
    for(int i=1;i<=t;i++){//及其稀少的主部分
        cnt=0;// 别忘记设0
        scanf("%lld%lld",&n,&m);
        for(long long j=0;j<=n;j++){
            cnt+=sum[j][min(m,j)];
        }
        printf("%lld\n",cnt);
    }
}

为什么用long long呢,因为乘的时候可能会出事

END

为什么计算机要学习数论呢,诶我桌子上怎么这么多头发… ]]>