机器学习之神经网络

2017-09-25

神经网络

more >>

展开全文 >>

高级算法-hash

2017-09-22

Hashing

1.Count Distinct Elements(可以解决莎士比亚文章中出现了多少个不同的词)

问题

Input：一个$x_1,x_2,x_3,…,x_n \in Q$的集合

Ouput：估计这个集合不同元素的个数 $z = |{x_1,x_2,…,x_n}| $

Uniform hash function $h: \Omega \rightarrow [0,1]$

用一个hash函数将x集合根据均匀分布映射到[0,1]的实数区间内。

$h(x_1),…,h(x_n): $z uniform independent values in [0,1]（因为有z个不同的元素，所以可以将这个区间划分成z+1块区域,h(x)表示当前点x映射到[0,1]的实数)
$$
X = min_{1 \le i \le n}{h(x_i)} \\
F(X) = P[X \ge x] = (1-x)^z \\
E[X] = \int_0^1{xP(x)}dx = \int_0^1{F(x)}dx = \frac {1}{z+1}(1-x)^{z+1}|_0^1 = \frac {1}{z+1}
$$

more >>

展开全文 >>

高级算法-多项式一致性检测

2017-09-14

Polynomial Identity testing(PIT)

单元多项式一致性检测

问题

2个d阶多项式$f,g \in 𝔽[x] $，判断$f \equiv g$ ?

因为f,g均为d阶多项式，所以$f-g$也是d阶多项式，所以问题其实就能等价于

判断$f \equiv 0$ ? f是通过黑盒给出，我们可以传入参数得到结果，但无法获知每一项的系数进行简单的比较

重要定理：n阶多项式最多有n个不同的解。

简单随机算法：

给定$S \subseteq 𝔽$，随机从S中选择一个r，判断f(r) = 0 , 如果不等于那么$f \not\equiv 0$，否则判定$f \equiv 0$的错误率就是$Pr[one-side \space error] \le \frac{d}{|S|}$。

将|S|中的元素数量设置成2d个，那么一次随机过程的错误率就降低到了1/2，进行logn次随机过程

$Pr[logn-sides \space error] \le \frac{1}{n}$。

more >>

展开全文 >>

群论-伽罗华域(有限域)学习

2017-09-14

伽罗华域

域

一组元素的集合，以及在集合上的四则运算，构成一个域。其中加法和乘法必须满足交换、结合和分配的规律。加法和乘法具有封闭性，即加法和乘法结果仍然是域中的元素。

域中必须有加法单位元和乘法单位元，且每一个元素都有对应的加法逆元和乘法逆元。但不要求域中的 0有乘法逆元。

more >>

展开全文 >>

关于所有2次幂数字组合方法相加为n的方法数(每个最多使用两次)

2017-09-13

题目

给你1,2,4,8,….所有2次幂的数字各两个，你有多少种取的方法保证取得数字和为n(1<=n<=10^18)

不同的方法表示至少有一种数字取的个数不同

more >>

展开全文 >>

组合数学-1

2017-09-11

f: N -> M 将n个求放入m个盒子中的多种方式

distinct: 不同 identical: 相同

balls per bin	unrestricted	<=1	>=1
n distinct balls , m distinct bins	$m^n$	$(m)_n$	$m!\begin{Bmatrix} m \ n \end{Bmatrix}$
n identical balls , m distinct bins	$(\binom{n}{m})= \binom{n+m-1}{m-1}$	$\binom{m}{n}$	$\binom{n-1}{m-1}$
n distinct balls , m identical bins	$\sum_{i=1}^m \begin{Bmatrix} n \ i \end{Bmatrix}$	$\begin{cases} 1 &n \le m \ 0 & n>m \end{cases}$	$\begin{Bmatrix} n \ m \end{Bmatrix}$
n identical balls , m identical bins	$\sum_{i=0}^m{p_i(n)}$ (当m>=n时也可以直接表示为p(n))	$\begin{cases} 1 &n \le m \ 0 & n>m \end{cases}$	$p_m(n)$

more >>

展开全文 >>

划分函数-整数拆分-and-五边形定理

2017-09-11

整数拆分

一个正整数可以写成一些正整数的和。在数论上，跟这些和式相关的问题成为整数分拆、整数剖分、整数分割、分割数或划分数。最常见的问题就是给定正整数n，求不同数组$(a_1,a_2,…,a_k)$的数目，符合下面的条件：

$a_1+a_2+ … +a_k = n (k大小不定)$

$a_1 \ge a_2 \ge … \ge a_k > 0$

其他附加条件(例如限定”k是偶数”，或”$a_i$不是1就是2”等)

分割函数p(n)就是求符合以上第一个和第二个调教的数组数目。

more >>

展开全文 >>

数学公式笔记

2017-09-09

1.斯特林公式

当k较大时

$k! \quad约等于 \quad k^{k+1/2}e^{-k} \sqrt{2 \pi}$

2.平方和公式
$$
f(n) = \sum_{i=1}^n{i^2} = 1/6n∗(n+1)(2n+1)
$$
*3.立方和公式

数学归纳法易证
$$
f(n) = \sum_{i=1}^n{i^3} = (\sum_{i=1}^n{i})^2
$$
4.莫比乌斯反演公式（线性筛法）

可参考贾志鹏线性筛
$$
n = \sum_{d|n} \phi(d) \quad (\phi(x)表示小于x的且与x互质的自然数的个数，这是个积性函数) \\
[n=1] = \sum_{d|n} \mu(d)
$$
5.泰勒展开式
$$
f(x) = \sum_{i=0}^\infty f^{(i)}(x_0) / (i!) ∗ (x-x_0)^i \quad f^{(i)}(x)表示f(x)的i次导数 \\
= \frac{f^{}(x_0)}{0!} + \frac {f^{‘}(x_0)}{1!}(x-x_0) + \frac {f^{‘’}(x_0)}{2!}(x-x_0)^2 + … + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n + R_n(x)
$$
由泰勒展开式可推出
$$
e^x = \sum_{i=0}^\infty x^i / i! \quad (泰勒展开时x0=0)
$$

展开全文 >>

莫比乌斯反演解决euler71

2017-09-09

题目

给你n，列出所有以1~n作为分母的最简分数按照从小到大排序。

当n=1000000时，求在3/7左侧第一个数的分子

（这个问题的思考过程中顺便解决了求解在x/y左侧一共有多少个数字的问题）

题目链接：https://projecteuler.net/problem=71

题解

一开始题目看错了，看成了求3/7左侧一共有多少个数。

最简单的想法是，对于1~n找到每个数作为分母的时候，小于3/7的分子的取值范围是[1,m]

那么在这n个循环的过程中，每次都在求解[1,m]有多少个数与作为分母的数互质

根据莫比乌斯反演的思想，参考贾志鹏线性筛：
$$
\sum_{d|n} \mu (d) = [n=1] \\
\begin{aligned}
\sum_{i=1}^m{[gcd(i,n)=1]} & = \sum_{i=1}^m{\sum_{d|gcd(i,n)}{\mu (d)}} \\
& = \sum_{i=1}^m{\sum_{d|i \space and \space d|n}{\mu (d)}} \\
& = \sum_{d|n}{\sum_{i=1 \space and \space d|i}^{m}{\mu (d)}} \\
& = \sum_{d|n}{\left\lfloor m/d \right\rfloor \mu (d)}
\end{aligned}
$$
每次循环里的一次操作只要考虑约数即可，在$O(\sqrt n)$解决，这个代码就呼之欲出了。但并没有达到题目要求解的答案。对于题目要求的球左侧第一个数字，我们可以对于每个分母，求出小于当前数字3/7的和分母互质的最大分子，这个求的方法就是利用求互质数字的个数二分求解。

这样总的时间复杂度就是$O(n \sqrt n logn)$，所以运行时间达到了48s…代码如下：


namespace euler71{
    int pri[N] , mu[N+5] , tot;
    bool vis[N+5];
    void mubius_init(int n)
    {
        clr(vis,0); tot = 0;
        mu[0] = 0 , mu[1] = 1;
        for(int i=2 ; i<=n ; i++){
            if(!vis[i]){
                pri[tot++] = i;
                mu[i] = -1;
            }
            for(int j=0 ; j<tot ; j++){
                if((LL)pri[j]*i>n) break;
                vis[pri[j]*i] = true;
                if(i%pri[j] == 0){
                    mu[i*pri[j]] = 0;
                    break;
                }
                else mu[i*pri[j]] = -mu[i];
            }
        }
    }
    //找到1~m中有多少个数和n互质
    int num_of_relative_prime(int m , int n)
    {
        int p = (int) sqrt(n+0.5);
        int res = 0;
        for(int d=1 ; d<=p ; d++){
            if(n%d == 0){
                res += mu[d]*(m/d);
                if(n/d != d){
                    res += mu[n/d]*(m/(n/d));
                }
            }
        }
        return res;
    }
    //找到m往左数第一个跟n互质的数字
    int bin_search(int m , int n)
    {
        int cnt = num_of_relative_prime(m, n);
       // cout<<"bin_search: "<<m<<" "<<n<<" "<<cnt<<endl;
        int lf=1 , rg=m , mid , ans=0;
        while(lf<=rg){
            mid = (lf+rg)>>1;
            if(num_of_relative_prime(mid, n) == cnt) ans = mid , rg = mid-1;
            else lf = mid+1;
        }
        return ans;
    }
	//本题要求的答案解决的接口，分母为1~n组合出的最简分数有序序列，输出x/y左侧第一个数的分子
    int solution(int x , int y , int n)
    {
        mubius_init(n);
        double mx = 0; 
        int numerator = -1; //分子
        int fraction = -1;
        for(int i=2 ; i<=n ; i++){
            int m = i*x/y;
            int val = bin_search(i==y?m-1:m , i);
            
            if(val<0) continue;
            if(val*1.0 / i > mx) mx = val*1.0 / i , numerator = val , fraction = i;
        }
        cout<<numerator<<"/"<<fraction<<endl;
        return numerator;
    }
    //求所有以1~n作为分母的小于1的最简分数小于x/y的数目
    LL solve(int x , int y , int n)
    {
        mubius_init(n);
        LL res = 0;
        for(int i=1 ; i<=n ; i++){
            int m = i*x/y;
            res = res+num_of_relative_prime(m , i);
           // cout<<i<<" "<<m<<" "<<res<<endl;
        }
        return res - 1; //自己本身被算了一遍
    }
}
int main()
{
    cout<<euler71::solution(3,7,1000000)<<endl;
   // cout<<euler71::solve(3,7,1000000)<<endl;
	return 0;
}
//428570/999997 , 对于euler71需要的答案是分子428570，running 48.224 seconds

但是这个做法显然太复杂又麻烦了，换个简单的方法就是，外层的n的循环对于每个分母都能找到一个最大的分子，无所谓他们是否互质，不互质就大家除以公约数即可，反正大小一定保证是最大的解。

namespace euler71{
    LL gcd(LL x , LL y){return y==0?x:gcd(y,x%y);}
    LL solve(int x , int y , int n){
        LL x1 = 0 , x2 = 1; //x1/x2
        for(int i=1 ; i<=n ; i++){
            LL m = (i*x-1)/y;
            if(x1*i < x2*m)
                x1 = m , x2 = i; 
           // cout<<i<<" "<<m<<" "<<res<<endl;
        }
        return x1/gcd(x1,x2); //自己本身被算了一遍
    }
}
int main()
{
    cout<<euler71::solve(3,7,1000000)<<endl;
	return 0;
}
//428570/999997 , 对于euler71需要的答案是分子428570，running 48.224 seconds

展开全文 >>

高级算法之Min-Cut问题求解

2017-09-08

问题：

将点集V分成S、T两个集合。使E(S,T)的边数量最少，求解最小割的值

本文将采用确定性网络流算法和非确定性随机算法两方面讲解，主要求解高级算法中的随机思想

more >>

展开全文 >>