2020牛客寒假算法基础集训营1 考点算法教程与例题集合

Anoyer

February 4, 2020

683views

No comments

3322 words

默认分类

2020牛客寒假算法基础集训营1 考点算法教程与例题集合

期望与概率

较好Blog：数论小白都能看懂的数学期望讲解 ,【整理】简单的数学期望和概率DP
例题：随机斐波那契，SP1026 FAVDICE - Favorite Dice , UVA12230 过河 Crossing Rivers, Help Me Escape，P4206聪聪与可可

尺取法

约数个数

其实这题没那么难优化什么的

$[1,n]$里约数有$i$的个数是$\lfloor\frac ni\rfloor$

所以$ans=\sum_{i=1}^n\lfloor\frac ni\rfloor$然后我们打表发现

有很多$\lfloor\frac ni\rfloor$都是一样的对于这些一样的数我们每次算一次似乎很浪费时间

所以我们每次 $i$ 跳到$\lfloor\frac nj\rfloor=\lfloor\frac ni\rfloor+1$这样的 $j$ 上对于中间一样的数一次性算掉

这样的复杂度又是多少呢?打表测试一下就好了复杂度$O(2\sqrt n)$//其实这道题数据范围可以出到$10^{14}$的 ~~手动滑稽~~

较好Blog：《数论从这里开始——一个数的因数》
例题：P1403约数研究

欧拉降幂

降幂公式：

$$ a^b \equiv \begin{cases}a^{b\%\varphi(p)} & gcd(a,p)=1\\a^b& gcd(a,p)\neq1,b<\varphi(p)\\a^{b\%\varphi(p)+\varphi(p)}&gcd(a,p)\neq1,b\geq\varphi(p)\end{cases} $$

较好Blog：前言1 --《欧拉函数》，前言2 -- 《欧拉定理 & 费马小定理》，《欧拉降幂和广义欧拉降幂》
例题：FZU1759- Super A^B mod C，HDU3221 - Brute-force Algorithm，HDU2837 - Calculation，HDU4335 - What is N?

矩阵快速幂

较好的Blog：《矩阵快速幂——入门》，《矩阵快速幂——进阶》，《矩阵快速幂——实战》
例题：矩阵快速幂专题

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int mod;
struct Matix{
    static const int _size=2;
    ll m[50][50];
    Matix(){
        memset(m, 0, sizeof(m));
    }
    void InitC(ll a=1){
        for(int i=0;i<_size;++i)m[i][i]=a;
    }
    Matix operator*(const Matix &m2){
        Matix t;
        for (int i = 0; i < _size; ++i)
            for (int j = 0; j < _size; ++j)
                for (int k = 0; k < _size; ++k)
                    t.m[i][j] = (t.m[i][j] + m[i][k] * m2.m[k][j]) % mod;
        return t;
    };
    ll* const operator [] (const int i){
        return m[i];
    }
    Matix operator^(int k) {
         Matix x = *this, ans;
         ans.InitC();        //初始化对角矩阵
         while (k) {
             if (k&1)
                 ans = ans * x;
            x = x * x;
            k >>= 1;
           }
           return ans;
      }
    Matix operator^(char *s){        //10进制快速幂
        Matix g = *this,res;
        res.InitC();
        int len=strlen(s);
        for(int i=len-1;i>=0;--i){
            if(s[i]!='0')res=res*(g^(s[i]-'0'));
            g=g^10;
        }
        return res;
    }
}g, u;
ll x[10];
char n[maxn];
int main(){
    ll a,b,ans=0;
    scanf("%lld%lld%lld%lld",&x[0],&x[1],&a,&b);
    scanf("%s%lld",n,&mod);
    g[0][0]=0,g[0][1]=1,g[1][0]=b,g[1][1]=a;
    u=g^n;      //求g的n次方
    for(int i=0;i<2;i++)ans=(ans+x[i]*u[0][i])%mod;
    printf("%lld\n",ans);
}