数学专题一日游

又是毕业季II

从n个数里面选k个数，求最大gcd
\(n \le 1e4, inf \le 1e6\)

题意 = 是 至少k个数 的因数的数的最大值
那么\(O(n * \sqrt {inf} )\)处理一下所有数的因数 记录每个因数出现了多少次
然后\(O(inf)\)处理一下f(k) 即出现k次的因数的最大值
最后\(O(k)\)转移 f(k) = max(f(k), f(k + 1))即可

阶乘问题

计算\(N(1 \le N \le 50,000,000)\)阶乘的最右边的非零位的值
hint: \(10,000,000!\) 有 \(2499999\) 个零

参考karma题解
一眼暴力可解 但注意如果每次 mod 10,会造成误差.因为当相乘后得到的是10的倍数时,mod 10 会变成0.
所以有三种方法

• 暴力 暴力乘,每次保留得到的数的后7位左右(保证不出现误差)
• 分析10怎么出现.发现如果两个数的因数中分别有2,5.那么相乘末尾一定有0.于是统计1~N中每个数的因数中2和5的个数.用2的个数减去5的个数(2的个数一定比5的个数多).剩下的是会对答案(即末尾的数)造成影响.之后大胆mod 10 就行了.
• N!的末尾只会是2,4,6,8(在此题中没有0).又[2,4,6,8]中任意一个数乘6,末尾仍是本身.2 * 6 = 12,末尾为2, 4 * 6 =24,末尾为4, 6 * 6=36,末尾为6,8 * 6 =48,末尾为8.又末尾数字只受末尾数字影响,如4. 4 * 6得到的末尾数字与4 * 16的末尾数字一样.又4 * 10=40,末尾数字为4(此题不要末尾0).则4 * 2 8==4 2 *5(意思是得到的末尾数字是一样的).故所有乘5的时候都可以换为乘8.又多次乘8末尾是有规律的.找出规律即可.（我太菜了没看懂 ）

计算系数

给定一个多项式\((by+ax)^k\) ，请求出多项式展开后\(x^n \times y^m\) 项的系数。

\[(ax+by)^k=\sum_{p=0}^kC_{k}^p(ax)^p(by)^{k-p}=\sum_{p=0}^k(C_{k}^pa^pb^{k-p})x^py^{k-p}\]

斐波那契公约数

Fibonacci数列第n项和第m项的最大公约数
\(n,m \le 10^9\)

由\(gcd(F[n],F[n+1])=1\)
推出结论：\(gcd(F[n],F[m])=F[gcd(n,m)]\)

• 来自five20的题解

花园

求有多少个长度为n的由P，C组成环， 满足环上任意m个相邻的字符，不超过K个是C
\(N \le10^{15}, 2 \le M \le 5, M \le N, ans \mod 1000000007\)

感觉可以用容斥做？【雾】
floyd矩阵快速幂
P = 1, C = 0 处理出长度为m的所有情况
再处理出转移（类似于最短路floyd那个转移
v = (u >> 1) & (1 << (m - 1)) 或 (u >> 1) 再判一下满不满足条件
然后快速幂n次 变成自己的就是符合条件的

[SCOI2010]生成字符串

求由多少个由n个1和m个0组成的字符串满足在任意的前k个字符中，1的个数不能少于0的个数。
\(1 \le m \le n \le 1000000, ans \mod 20100403\)

结论：\(C(n+m,m)?C(n+m,m?1)\)
xyz32768的题解

[JLOI2013]卡牌游戏

第一回合是玩家1作为庄家。
每个回合过程如下：

• 庄家随机从卡牌堆里选择一张卡片，卡片上的数字为X
• 顺时针从庄家位置数第X个人将被处决即退出游戏
• 卡片将会被放回卡牌堆里并重新洗牌
• 被处决的人按顺时针的下一个人将会作为下一轮的庄家
  已知有n个玩家，m张牌和它们的内容
  求每个玩家胜出的概率。
  \(1 \le N \le 50， 1 \le M \le 50, 1 \le 每张卡片上的数字 \le 50\)

概率dp
hint:概率dp好多都是逆推。。
直接dfs枚举的复杂度 对于每一轮枚举卡片种类\(O(m^n)\)
第一感觉矩阵快速幂 然鹅奇妙的奇数方式并不能直接乘
f[i][j]表示在还剩下i个人时，从庄家开始数第j个人的获胜的概率
显然f[1][1] = 1（最后一轮了嘛
那么f[i]可以从f[i - 1]推出来
枚举剩了i个人那轮 抽到的牌是多少 就能推出那轮的庄家和挂掉的人
累加就好啦

转移式转自钟梓俊的题解

当c>j时，\(f[i][j]=f[i][j]+\frac{f[i-1][i-c+j]}{m}\)
否则 当c<j时， \(f[i][j]=f[i][j]+\frac{f[i-1][j-c]}{m}\)

[SDOI2009]虔诚的墓主人

不是树的地方都是墓哦
\(ans \mod 2,147,483,648\)
\(1 ≤ N, M ≤ 1,000,000,000，0 ≤ xi ≤ N，0 ≤ yi ≤ M，\)
\(1 ≤ W ≤ 100,000，1 ≤ k ≤ 10\)

注意一下用树状数组是因为它常数小
它直接维护列上的答案贡献
Lance1ot的博客

[CQOI2007]余数求和

给出正整数 n 和 k 计算 \(G(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ n\)的值
\(n,k≤10^9\)

\(k \ \bmod\ i = k - \lfloor \frac{k}{i} \rfloor * i\)
那么原式就是\(k * n - \Sigma_{i = 1}^{n}{\lfloor \frac{k}{i} \rfloor * i}\)
\(O(ln \ n)\)暴力一下就好啦
每次求出一个除n下取整一样的区间 等差数列求和

[SCOI2005]扫雷

递推就可以了。。【想打人

2^k^进制数

高精 x 递推
f[i][j]第i位是j
\(f[i][j] = \Sigma_{k = j + 1}^{2^k - 1} f[i - 1][k]\)

[POI2007]ZAP-Queries

其实还是逃不开这个式子
\[\Sigma_{i = 1}^{n} \Sigma_{j = 1}^{m} [gcd(i, j) = d]\]
\[ = \Sigma_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \Sigma_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i, j) = 1] \]
\[ = \Sigma_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \Sigma_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \Sigma_{k | d} \ \mu (k)\]
\[ = \Sigma_{k = 1}^{\lfloor \frac{min(n, m)}{d} \rfloor} \ \mu (k) \lfloor \frac{n}{dk} \rfloor\lfloor \frac{m}{dk} \rfloor\]
然后貌似就没有什么问题了

[HAOI2011]Problem b

这不就是上一道题容斥一下么。。
ans(b, d) - ans(b, c - 1) - ans(a - 1, d) + ans(a - 1, c - 1)

[SDOI2015]约数个数和

根据一个令人头秃的公式
\[\sigma_{0}(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\]
然后我们就开心地反演吧//不对我式子推错了 等待update

数学专题一日游

原文：https://www.cnblogs.com/hjmmm/p/10433400.html