标签:: 数论

0

「组合数」错排问题

前言——为什么要写这篇文章学校数学学案上的一道计数原理的题目: 有4个小球和4个盒子,编号分别为1,2,3,4,要求编号为n的盒子不能放编号为n的小球,求一功能有多少种方法放球. ans = 44 我当时真的没有任何思路,上课讲也没怎么听懂,回家用把这道题用程序解了一下,代码如下: #include <iostream> #include <cstring> #include

0

「数论」启发式思路——fac数组存大整数

关于——为什么要写这个我们都用过杨辉三角递推式生成过杨辉三角,可是往往时间效率只能达到n<=5000,在学习完二项式定理之后得知一种新的直接递推第n行的杨辉三角数的公式 数组表达形式:line[n][x]=line[n][x-1]*(n-x+1)/x 终于可以O(n)求组合数了! 但是别高兴的太早,实测在不取模的情况下n=30就会爆int,而我们知道: (a+b)mod n=((a mo

0

「数论」杨辉三角预处理组合数

杨辉三角预处理组合数今天,我要和和大家好好研究一下杨辉三角为什么这么神奇! 引进需要数学基础并不是很多,高中狗都学过了: 排列组合 二项式定理 那么今天我们首先来研究一下组合数和杨辉三角的关系: 提到组合数,大家都不陌生了,下面上公式 可是,如果把这个公式直接模拟到程序中写了一套甚至带阶乘的代码显然是很不理智的行为,即使你用long long,因为组合数这种东西数一大真的很危险,不信你在Wo

0

「数论」Eratosthenes筛法和欧拉筛

前言我们今天要研究快速求质数的算法,比起普通的普通判断方法,今天所讲的方法更加的快速高效,如何判断质数在此不加赘述,请您往下看: Eratosthenes筛法Eratosthenes筛法又称普筛,易于初学者学习,因为其原理简单,代码简短实现容易,所以我看今天的时间不多,就给大家详细讲一讲Eratosthenes筛法。下面,进入正题: Eratosthenes筛法是一种用于筛范围质数的一种高效的算