[题目链接](https://ac.nowcoder.com/acm/contest/297/D) ------------ 定义有n张纸币，且存在m，使得这n张纸币可以通过任意组合构成不超过m元的任意值，则n符合 用a[n+1]表示第n+1张纸币的值，当a[n+1] <= m+1 时n+1才符合 证明： 反证法：若a[n+1] > m+1，那么无论n+1张纸币如何组合，都无法构成m+1元 注意：计算前要将a[n]进行从小到大排序 ------------ 代码 #include <bits/stdc++.h> using...

常见的积性函数： 单位函数：$e(n)=[n=1]$ 欧拉函数：$\varphi (n)=\sum_{i=1}^{n}[gcd(i,n)=1]=n\prod_{i=1}^{k}(1-\frac{1}{p_{i}})$ 幂函数：$Id_{a}(n)=n^{a}$ 除数函数：$\sigma (n)=\sum_{d|n}^{n}d$ 莫比乌斯函数：$\mu (n)=[max(c_{1},c_{2}...c_{k})\leq 1](-1)^{k}$ ------------ $Dirichlet$卷积 $h(n)=(f*g)(n)=\sum_{i|n}f(i)g...

巴什博奕(Bash Game): 只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜 ........................................................................................................ 结论：若(m+1) | n，则先手必败，否则先手必胜 显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜 因此我们发现了如何取胜的法则： 如果n=(m+1)r...

系数表示法： 设A是一个很大的数 A = $a_{0}$ + $a_{1}*x$ + $a_{2}*x^{2}$ + ... $a_{n-1}*x^{n-1}$ $a_{0}$ $a_{1}$ $a_{2}$  ... $a_{n-1}$  分别表示A的第一位、第二位 ... 第n位，这样，向量($a_{0}$, $a_{1}$, $a_{2}$,  ... $a_{n-1}$)就表示了A ------------ 点值表示法： 令A ( x )= $a_{0}$ + $a_{1}*x$ + $a_{2}*x^{2}$ + ... $a_{n-1}...

由外向内去计算每一点能积累水的体积，一点处的水的体积取决于这一点和其四周的高度，用优先队列维护当前更新的点，每次取出高度最低的点，去更新其四周的点，再将四周的点放入队列 最后答案就是每一点更新后与原来的高度差总和 #include <bits/stdc++.h> using namespace std; #define mset(var,val) memset(var,val,sizeof(var)) #define rep(i,x,n) for(int i=x;i<n;i++) #define rep1(i,x,n) for(int i=x;i<=n;i...

题目：https://ac.nowcoder.com/acm/contest/326/C 先用bfs求从a走到b的步数，用二维数组dis保存 (dis[a][b]表示从a到b操作的最少次数) 对于a==b或者b>233的情况直接输出答案 因为a是可能大于等于233的，所以每次不是直接输出dis[a][b]， 而是求出f=F(a)和g=G(a)的值，讨论情况 dis[f][b]和dis[g][b]都不存在，输出-1 dis[f][b]和dis[g][b]有一个存在，输出的答案要加1，因为a转化为f...