定义：定义贝尔数 $B_n$ 为：$n$ 个元素划分为任意个集合的方案数。由第二类斯特林数定义可得： $$B_n=\sum_{i=0}^{n}\begin{Bmatrix}n\cr i\end{Bmatrix}$$ 递推式： $$B_{n+1}=\sum_{i=0}^{n}\binom{n}{i}B_i$$ 由此可以 $O(n^2)$ 递推； To…

题目链接：hdu4651 Partition 动规做法 设 $f[n][m]$ 为 $n$ 个球放到 $m$ 个盒子里的方案数。则 $n$ 的整数拆分方案等于 $f[n][n]$。 如果只有一个盘子或者没有小球，方案数自然为 $1$ 如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移 $f[i][j]=f[i][i]$ 如果小球…

默认问题为 $n$ 个小球放到 $m$ 个盒子里： 球相同，盒子不同，不能有空盒 实质就是把 $n$ 个小球分为 $m$ 组（不能空）。利用插板法，就是在 $n$ 个小球的 $n-1$ 个空隙当中刚好插入 $m-1$ 个板子，即恰好分为不为空的 $m$ 组。 $$ans=\binom{n-1}{m-1}$$ 球相同，盒子不同，可以有空盒 对于每个盒…

题目链接 SGU106 题目大意 已知$a,b,c,xl,xr$，求方程$ax+by+c=0$,$x\in[xl,xr],\ y\in[yl,yr]$的整数解个数.所有数不大于 $10^8$ 解题思路 将上式转化成 $ax+by=-c$。令 $c=-c$，即 $ax+by=c$。 将此时的$a,b,c$变成正数： 如果 $c<0$，则 $a,…

题目链接： 洛谷P1835 素数密度 题目大意： 给定区间$[L，R],(L≤R≤2147483647,R-L≤1000000)$，请计算区间中素数的个数。 #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 50; const int LEN = 1e6 …

51nod 1060 最复杂的数 51nod 1060 最复杂的数 题目大意： 把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。$(n\le 10^{18}, T\le 100)$ 例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。 即求 $n$ …

51nod 1061 最复杂的数V2 51nod 1061 最复杂的数V2 题目大意： 把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。 例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。 即求 $n$ 以内最大的反素数。 数据范围： $n\le …

P2480 [SDOI2010]古代猪文 题目大意： 给定 $G,n$，$1\le G,n\le 10^9$，求： $$ G^{\sum_{k|n}\binom{n}{k}}\bmod 999911659 $$ 分析： 由于 $P=999911659$ 是质数，所以当 $G\bmod P=0$ 时，答案为 $0$；否则： $$ ans=G^{\su…

2019牛客多校第五场C generator3 题目大意： 给你 $n,x_0,a,b,p$，$x_i=(a\cdot x_{i−1}+b)\bmod p$。给你 $q$ 组询问 $v$，问你各个 $x_i(i\in[0,n-1])$ 中最小的 $i$ 使得 $x_i=v$ 。$(1\leq n≤10^{18},\ 0\leq x_p,a,b &l…

2019南京网络赛 E. K SUM 题目大意： $$ f_n(k)=\sum_{l_1=1}^n \sum_{l_2=1}^n ... \sum_{l_k=1}^n \left(\gcd\left(l_1,l_2,...,l_k\right)\right)^2 $$ $$ 1 \le n \le 10^9,2 \le k \le {10}^{10…