标签 - 原创

? 原创 ? ? Miller_rabin ? ? Pollard_rho ?    2021-02-28 20:41:50    1375    0    0
数论小专题——因数的分解 一、大整数质数探测 Miller_rabin算法 p" role="presentation">ppp是质数,费马小定理 ap−1=1(mod p)" role="presentation">ap−1=1(mod p)ap−1=1(mod p)a^{p-1}=1(mod\ p) p​" role="presentation">p​p​p​是质数,x2=1(mod p)→x=1 or&#xA
? 原创 ? ? FMT|FWT ?    2018-11-19 08:16:13    8189    12    7
1、快速莫比乌斯变换 1.1 什么是莫比乌斯变换    快速莫比乌斯变换,简称(FMT),也是一种对数列的变换。类似FFT地,FMT也是通过将数列/多项式在两种形式下来回变换达到加速两个数列/多项式卷积的效果。    FFT解决的是这样的卷积:    Cx=∑i+j=xaibj" role="presentation" style="position: relative;">Cx=∑i+j=xaibjCx=∑i+j=xaibj C_x=\sum_{i+j=x}a_ib_j    其中x,i,j" role="presentation" style=
? 原创 ?    2018-11-13 09:25:17    634    0    0
原来一直只把调和级数(Hn" role="presentation" style="position: relative;">HnHnH_n)当成算复杂度的工具。 直到遇到了这样一道题: T2062 随机数生成器 通过打表可以发现,答案就是Hn+1" role="presentation" style="position: relative;">Hn+1Hn+1H_n+1 但是n" role="presentation" style="position: relative;">nnn太大,调和数本身也没有通项公式。 在说这道题之前,我们先来说说调和数是什么吧
? 原创 ?    2018-03-14 20:00:11    294    1    1
pdf以及std:难题选讲2.zip 引言:有一类数据结构题型略微奇妙,下面是一个例子。 CF259 Div1 E. Little Pony and Lord Tirek 时间限制:3000ms|空间限制:256MB 半人马提雷克是“我的小马驹:友谊是魔法”第四季最后两集的大反派。在“闪闪王国(上)”中,提雷克从塔他洛斯逃了出来。为了变得更加强大,他还吸取了小马们的魔法。 提雷克的核心技能是法力吸取。这个技能可以吸收一个魔法生物的所有魔力并把它们交给施法者。 现在我们把这个问题简化,假设你有n只小马(编号从1到n)。每只小马有三种属性。 si:时间为0时这只小马拥有
? 原创 ?    2018-03-13 13:39:01    272    0    0
PDF以及配套数据下载地址:难题选讲2-送你一公式数论-Rockdu.rar 引言:有一类数论问题,考察数学公式的灵活运用与变换。我们来看一个例子: 最小公倍数之和 V3 时空限制:1s / 256MB 出一个数N,输出小于等于N的所有数,两两之间的最小公倍数之和。 相当于计算这段程序(程序中的lcm(i,j)表示i与j的最小公倍数): 由于结果很大,输出Mod 1000000007的结果。 G=0;for(i=1;i< N;i++)for(j=1;j<=N;j++){ G = (G + lcm(i,j)) % 1000000007;}
? 原创 ?    2018-01-26 17:50:39    183    0    0
PDF以及配套数据下载地址:难题选讲1-送你一序列字符串-Rockdu.rar 浅谈一类字符串问题 引言:有一类不常规的序列上字符串问题十分的特别。下面我们来看一个例子。 所有公共子序列问题V2 时空限制:1s/256MB 题目描述: 给定长度分别为n, m的只包含小写字母的串A, B。你需要输出A、B所有本质不同的公共(或公共回文)子序列的个数,答案对66662333取模。详见数据范围。(空序列算作回文序列) 输入格式: 一行n, m, k, k作为子问题标识 第二行长度为n的字符串,表示A 另一行长度为m的字符串,表示B
? 原创 ? ? 生成函数 ?    2018-01-15 21:18:24    613    0    0
泰勒展开-皮亚诺余项: *本文中f(i)&#x90FD;&#x6307;f&#x7684;i&#x9636;&#x5BFC;&#x6570;" role="presentation" style="position: relative;">f(i)都指f的i阶导数f(i)都指f的i阶导数f^{(i)}都指f的i阶导数 f(x)=(&#x2211;i=0&#x221E;f(i)(x0)(x&#x2212;x0)ii!)+o[(x&#x2212;x0)&#x221E;],o[(x&#x2212