简单数论回顾

近期题单一览

时间:20201102~20201120

✔hdu1061,求$n^n$的末尾数字

✔hdu3117,矩阵快速幂算Fib数列

✔hdu6030,递推数列转为矩阵,再进行快速幂取模

✔hdu1576,拓展欧几里得

✔hdu2588,欧拉函数复习

✔hdu5656,有关GCD的动态规划(另解:容斥)

✔poj2689,区间素数板子

✔hdu3792,素数打表可做

✔hdu2841,容斥原理

✔hdu4135,容斥原理

✔hdu1028,递归/DP/生成函数

✔hdu1521,指数型生成函数

✔hdu5673,卡特兰数+逆元

✔hdu2999,SG函数

✔hdu1527,威佐夫博弈

部分题解

HDU5656

这道题目有很多解法,可以动态规划,可以容斥原理,还可以莫比乌斯函数(这个我没写)。

思想比较妙,因为这些数字都很小,所以可以开一个桶把GCD值对应的方案数直接存到数组里,即num[gcd的值] = 方案数这样。而后,枚举gcd的值而不是去枚举方案,即可得出答案。

这种用桶去存储的思路在上次某道贪心题小结里面也有出现,上次是以其中一个变量为关键词排序,另外一个变量(数字很小)直接枚举,看桶里是否有可以取出来的元素。

定位好要用桶来解决问题之后就好办了。

如果选择动态规划,设置dp[前i项任意选择][选择出来的GCD值为j],有:

  1. $i-1$中能够选出$j$来,则$i$也必定能够选出$j$来。
  2. 若当前枚举到的$j$能够在$i-1$下枚举出来,则$a[i]$参与后有贡献dp[i][gcd(a[i], j)]

整理后,得到:

① $dp[i][j] = dp[i][j] + dp[i-1][j]$

② $dp[i][gcd(a[i], j)]=dp[i][gcd(a[i], j)] + dp[i-1][j]$

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define maxn 1005
#define mod 100000007
using namespace std;
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
long long t, n, a[maxn], dp[maxn][maxn];
signed main(void)
{
scanf("%lld", &t);
while(t--)
{
long long maxx = 0;
memset(dp, 0, sizeof(dp));
scanf("%lld", &n);
for(register int i = 1; i <= n; i++) scanf("%lld", &a[i]), maxx = max(maxx, a[i]);
for(register int i = 1; i <= n; i++)
{
dp[i][a[i]] = 1;
for(register int j = 1; j <= maxx; j++)
{
dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
if(dp[i-1][j])
dp[i][gcd(a[i], j)] = (dp[i][gcd(a[i], j)] + dp[i-1][j]) % mod;
}
}
int sum = 0;
for(register int i = 1; i <= maxx; i++)
sum = (sum + i * dp[n][i]) % mod;
printf("%lld\n", sum);
}
return 0;
}

当然,你也可以使用容斥原理。

定义$g[i]$为选择出来的数的GCD值为i的倍数的方案数。

由子集性质,可得方案数为$g[i]=2^{num[i]}-1$,$num[i]$为数组$a$中能够被$i$整除的数。

后面,枚举倍数$j$,求得$g[i] = g[i] - g[i*j]$,得到GCD值刚好为$i$的方案数。

后续统计答案即为$\sum i*g[i]$。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define maxn 1005
#define mod 100000007
using namespace std;
long long t, n, a[maxn], num[maxn], g[maxn];
long long gcd(long long a, long long b){
return b ? gcd(b, a % b) : a;
}
long long qpow(int a, int b, int p){
if(b == 0) return 1;
if(b == 1) return a;
long long tmp = qpow(a, b / 2, p);
tmp = (tmp * tmp) % p;
if(b & 1) tmp = (tmp * a) % p;
return tmp;
}
signed main(void)
{
scanf("%lld", &t);
while(t--)
{
memset(num, 0, sizeof(num));
memset(g, 0, sizeof(g));

scanf("%lld", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

for(int i = 1; i <= n; i++)
for(int j = 1; j <= 1000; j++)
if(a[i] % j == 0) num[j]++;

for(int i = 1; i <= 1000; i++)
g[i] = qpow(2, num[i], mod) - 1;

for(int i = 1000; i >= 1; i--)
for(int j = 2; j * i <= 1000; j++)
g[i] = (((g[i] - g[i * j]) % mod) + mod) % mod;

long long ans = 0;

for(int i = 1; i <= 1000; i++)
ans = (ans + i * g[i]) % mod;

printf("%lld\n", ans);
}
return 0;
}

这题的确是很不错的题目。

然后,据说能莫比乌斯反演…我还是先不写了,我现在太菜了呜呜呜。


POJ2689

区间素数模板。

  1. 筛选出$[1, \sqrt{max_{rt}}]$区间内的所有素数。如果是int范围内,大概就是五万内的素数。
  2. 利用这些素数对需要求的区间进行筛选标记。

不过我被一个小小的坑点坑到了,具体坑点看代码注释。

其他思路都很好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define int long long
#define maxn 5000005
using namespace std;
int lf, rt, cnt, isp[maxn], sp[maxn];
bool iisp[maxn];
//第一轮筛选
void euler(int lim){
memset(iisp, true, sizeof(iisp));
iisp[1] = false;
for(int i = 2; i <= lim; i++)
{
if(iisp[i])
{
cnt++;
sp[cnt] = i;
}
for(int j = 1; j <= cnt && i * sp[j] <= lim ; j++)
{
iisp[i * sp[j]] = false;
if(i % sp[j] == 0) break;
}
}
}
signed main(void)
{
euler(50000);
while(~scanf("%lld %lld", &lf, &rt))
{
//第二轮筛选
memset(isp, 0, sizeof(isp));
if(lf == 1) isp[0] = 1;
for(int i = 1; sp[i] * sp[i] <= rt && i <= cnt; i++)
{
int st = lf / sp[i];
//此处之前踩了坑,少了sp[i] * st < lf这个条件
//可用 10000 / 4999 = 2,卡掉(数组越界)
while(st <= 1 || sp[i] * st < lf) st++;
for( ;sp[i] * st <= rt; st++)
isp[sp[i] * st - lf] = 1;
}
int maxx = -1, minn = (1 << 30), las = -1;
int ma_l, ma_r, mi_l, mi_r;
for(int i = 0; i <= rt - lf; i++)
{
if(!isp[i] && las == -1) las = i;
else if(!isp[i] && las != -1)
{
if(i - las > maxx)
{
maxx = i - las;
ma_l = lf + las;
ma_r = lf + i;
}
if(i - las < minn)
{
minn = i - las;
mi_l = lf + las;
mi_r = lf + i;
}
las = i;
}
}
if(!(~maxx))
printf("There are no adjacent primes.\n");
else
printf("%lld,%lld are closest, %lld,%lld are most distant.\n", mi_l, mi_r, ma_l, ma_r);
}
return 0;
}

HDU2841

这题有两种做法,一个是容斥原理,一个是莫比乌斯反演。

其中,在$n=m$时,可以转化为欧拉函数求解(典型题目参考”SDOI2008仪仗队“)。

其示意图如下:

仪仗队

该题存在$n \neq m$的情况,考虑容斥原理。

首先,只有坐标互质的点才能被看见。

简要证明如下:

假设坐标$(x, y)$不互质,可设$d = gcd(x, y)$,即存在$x’ = x / d$,$ y’ = y / d$,易得$(x’,y’)$会阻挡看向$(x, y)$的视线。

故得只有坐标互质的点才能被看见。

然后,问题转化为求互质坐标的数目。

互质相对来说比较难求,我们转化为求不互质的坐标。

先考虑简单一些的一维情况(HDU4135,该题弱化版):

  • $Problem:\ $求解$[1, m]$上所有能被$n$整除的点。

也就是求$\sum_{i=1}^{m} [gcd(n, i) = 1]$,其中$[表达式]$表示当括号内表达式为真时返回$1$否则为$0$。

不妨先对$n$分解质因数,得$p_1,p_2,p_3,…,p_n$。

然后,容斥开始,容斥的复杂度是$O(2^k)$,$k$为因子数,本题数据较小可以使用。

对于单一一个素数,贡献值为$\lfloor m/p_i \rfloor$,将其添加到答案中。

对于任意两个素数积,贡献值为$\lfloor m/(p_i * p_j) \rfloor$,将其从答案中减去(去重)。

对于任意三个素数积,贡献值为$\lfloor m/(p_i p_j p_k) \rfloor$,将其添加到答案中。

以此类推…

如果对这个过程不是很理解,可以手玩下面这道容斥的例题:

1
假设班里有10个学生喜欢数学,15个学生喜欢语文,21个学生喜欢编程,班里至少喜欢一门学科的有多少个学生呢?

设三个集合分别为$A,B,C$,则:

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$

通过这个例子可以很容易理解为什么上面容斥是这么做的。

推广后,可得当交起来的集合数量是偶数时为减去贡献值,交起来的集合数量是奇数时为加上贡献值。

明白原理后,就可以开始写代码了。

既然是一个类似取或不取(质因数)的问题,那么就可以利用二进制来表示,1代表取该因子,0代表不取,枚举每一个状态,其中利用$lowbit$和对数确定取得是哪个集合,将它的贡献值乘上去(即求$p_ip_jp_k*…p_?$这样子)。

具体实现看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int lowbit(int x){
return x & (-x);
}
int cnt_one(int x){
int cnt = 0;
while(x) x -= lowbit(x), cnt++;
return cnt;
}
int bas[maxn];
int calc(int n, int m){
bas[0] = 0; int f = 0;

for(int i = 2; i * i <= m; i++)
{
if(m % i) continue;
while(m % i == 0) m /= i;
bas[++bas[0]] = i;
}
if(m > 1) bas[++bas[0]] = m;

for(int i = 1; i <= (1 << bas[0]) - 1; i++)
{
int flag = cnt_one(i) & 1 ? 1 : -1;
int now = 1, tmp = i;
while(tmp)
{
now *= bas[(int)log2(lowbit(tmp)) + 1];
tmp -= lowbit(tmp);
}
//printf("%d %d\n", f, n / now);
f += flag * (n / now);
}
return n - f;
}
signed main(void)
{
int t, cases = 0;
scanf("%lld", &t);
while(t--)
{
int a, b, m;
scanf("%lld %lld %lld", &a, &b, &m);
printf("Case #%lld: %lld\n", ++cases, calc(b, m) - calc(a-1, m));
}
return 0;
}

至于难一点的二维情况,由于数据较小,可以直接枚举每一个一维情况,就能得到答案。

这里不再叙述。

除了使用普通的容斥原理,还可以使用莫比乌斯反演(这也是容斥推导出来的)。

该题实际上就是求:$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i, j) = 1]$

实际上,这条式子(求互质数数目)是非常常用的。

关于反演的前置知识此处不做叙述,直接开始推式子(假设$n \leq m$):

$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i, j) = 1]$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i, j)}μ(d)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}μ(d)*[d|gcd(i, j)]$

$=\sum_{d=1}^{n}μ(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i, j)]$

$= \sum_{d=1}^{n} μ(d) \frac{n}{d} \frac{m}{d}$

推到这里就可以数论分块了。

做一个莫比乌斯函数的前缀和,就可以在$O(\sqrt n)$的复杂度中完成该题了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int t, n, m;
int cnt, mu[maxn], pri[maxn], sum[maxn];
bool isp[maxn];
void euler(int lim){
memset(isp, true, sizeof(isp));
isp[1] = false;
mu[1] = 1; sum[1] = 1;
for (int i = 2; i <= lim; i++)
{
if (isp[i])
{
pri[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= cnt && pri[j] * i <= lim; j++)
{
isp[pri[j] * i] = false;
if(i % pri[j] == 0) break;
mu[pri[j] * i] = -mu[i];
}
sum[i] = sum[i-1] + mu[i];
}
}
signed main(void)
{
euler(100000);

scanf("%lld", &t);
while (t--)
{
scanf("%lld %lld", &n, &m);
if (n > m)
swap(n, m);

int ans = 0, r;

for(int i = 1; i <= n; i = r + 1)
{
r = min(n / (n / i), m / (m / i));
//printf("%lld %lld %lld\n", i, r, sum[r]-sum[i-1]);
ans += (sum[r]-sum[i-1])*(n/i)*(m/i);
}
printf("%lld\n", ans);
}
return 0;
}

HDU1028

递推/记忆化搜索/生成函数均可做。

首先写一下记忆化搜索的思路,设立状态$dp[n][m]$。

具体意义,利用另一个相同的例题(POJ1664)理解更容易。

即设$n$为苹果数目,$m$为碟子数目,$dp[n][m]$为将$n$个苹果分到$m$个碟子中的数目,允许有空碟子。

开始分类讨论:

  • 【边界情况】当$n=0$时,即没有苹果了,方案数为$1$。

  • 【边界情况】当$m = 1$时,即只有一个碟子,方案数也为$1$(全都放到一个盘子里)。

  • 当$n < m$时,即不可能放完所有的盘子,此时方案数与$(n, n)$相同(不计顺序)。

  • 当$n \ge m$时,此时分为两种情况,存在空盘子和不存在空盘子:

    存在空盘子时,方案数与$(n, m-1)$相同,即$m-1$个盘子均放满,或存在空盘子。

    不存在空盘子时,方案数与$(n-m, m)$相同,即每个盘子都至少放了一个苹果。

由此写出对应的转移方程即可。

记忆化搜索代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define maxn 1005
#define int long long
using namespace std;
int n, dp[maxn][maxn];
int solve(int n, int m){
if(n == 0 || m == 1) return dp[n][m] = 1;
if(dp[n][m]) return dp[n][m];
if(n < m)
return dp[n][m] = solve(n, n);
if(n >= m)
return dp[n][m] = solve(n-m, m) + solve(n, m-1);
}
signed main(void)
{
while(~scanf("%lld", &n))
printf("%lld\n", solve(n, n));
return 0;
}

一个道理,可以改写成递推形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define maxn 1005
#define int long long
using namespace std;
int n, dp[maxn][maxn];
signed main(void)
{
while(~scanf("%lld", &n))
{
for(int i = 0; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i == 0 || j == 1)
{
dp[i][j] = 1;
continue;
}
if(i < j)
dp[i][j] = dp[i][i];
if(i >= j)
dp[i][j] = dp[i-j][j] + dp[i][j-1];
}
printf("%d\n", dp[n][n]);
}
return 0;
}

由这样的递推关系,我们还可以使用普通型生成函数来解决这个问题。

生成函数最重要的思想:把组合问题的加法与幂级数的乘幂对应起来。

罗勇军老师的书对这一块讲的很好,转载如下:

首先设计函数:

$g(x) = (x^{0 1}+x^{1 1}+x^{2 1}+…) (x^{0 2}+x^{1 2}+x^{2 2}) …$

即为:

$g(x)=(1+x+x^2+x^3+…) (1+x^2+x^4+…) (1+x^3+x^6+x^9+…) * …$

其中:
$(x^{0 1}+x^{1 1}+x^{2 * 1}+…)$分别代表不用数字$1$,用一次数字$1$,用两次数字$1$,以此类推。

这样子,寻找$x^n$的系数,就是我们最后要找的答案。

这样的普通型生成函数用于解决组合问题,指数型生成函数用于解决排列问题。

在想不到动态规划的转移方程的时候,可以考虑用生成函数,思路更为直观清晰。

生成函数的解法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define maxn 1005
#define int long long
using namespace std;
int n, c1[maxn], c2[maxn];
signed main(void)
{
while(~scanf("%lld", &n))
{
for(int i = 0; i <= n; i++)
c1[i] = 1, c2[i] = 0;
for(int k = 2; k <= n; k++)
{
for(int i = 0; i <= n; i++)
for(int j = 0; j + i <= n; j += k)
c2[i + j] += c1[i];
for(int i = 0; i <= n; i++)
c1[i] = c2[i], c2[i] = 0;
}
printf("%lld\n", c1[n]);
}
return 0;
}

HDU1521

指数型生成函数板子题。

假设有两个物品$A$,构造如下:$(\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!})$,其中各项系数(此处均为$1$)代表选$k$件A的排列数,$k$为幂次。

另外,除以阶乘是因为要删除重复的排列,例如$A_1BA_2$和$A_2BA_1$是同一种方案,$A_1A_2$的排列数为$2!$,由此得到分母应为$2!$。

拓展到多个物品,两个物品$A$,三个物品$B$,一个物品$C$,构造生成函数如下:

$g(x)=(\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}) (\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}) (\frac{1}{0!})$

最后,取幂次为$m$的项的系数,就是要求的答案。

阶乘需要特殊处理一下,处理乘法时直接除多一项,最后统计答案时再乘上$m!,$就可以化出对应答案。

具体看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int n, m, a[maxn];
double c1[maxn], c2[maxn];
double fl(int x){
double tmp = 1;
for(int i = 1; i <= x; i++)
tmp *= i;
return tmp;
}
signed main(void)
{
while(~scanf("%lld %lld", &n, &m))
{
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));

for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

for(int i = 0; i <= a[1]; i++)
c1[i] = 1.0 / fl(i), c2[i] = 0;

for(int k = 2; k <= n; k++)
{
for(int i = 0; i <= m; i++)
for(int j = 0; j <= a[k] && i + j <= m; j++)
c2[i+j] += c1[i] / fl(j);

for(int i = 0; i <= m; i++)
c1[i] = c2[i], c2[i] = 0;
}
printf("%.0lf\n", c1[m] * fl(m));
}
return 0;
}

HDU5673

这题可以看成卡特兰数板子题的增强版,增加了可以原地不动的操作。

那么我们就可以,枚举到底左右各移动多少次(至多$\lfloor n/2 \rfloor$次),这部分是否合法用卡特兰数思路去做(同规范01序列那题)。

就可以得到答案$\sum_{i=0}^{\lfloor n/2 \rfloor} C_{n}^{2i}*Catalan(i)$

这一题比较难的点,还是在逆元的求解。

逆元求解主流有四种考法,拓展欧几里得,费马小定理,线性求逆元,阶乘求逆元。

下面再简单总结一下:

  • 拓展欧几里得

    求解不定方程$ax+by=c$的特殊情况$(c = 1)$。

    的逆元即为满足$ax \equiv 1(mod \ b)$的数$a$,这条式子又可转为$ax + by = 1$,因此可用$exgcd$求解。

  • 费马小定理(求单个数的逆元,要求$a \perp p$,且$p$为素数)

    使用这种情况求逆元时,只需求得$a^{p-2} \ mod \ p$。

    由小定理,有$a^{p-1} \equiv 1 (mod \ p)$,

    即有$a * a^{p-2} \equiv 1 (mod \ p)$。

    故,$a^{p-2}$为$a$在$mod \ p$意义下的逆元,用快速幂求解即可。

  • 线性递推(递推求一串数的逆元,例如$1-n$)

    对于边界情况$x=1$时,$x^{-1} = 1$

    对于其他情况$x=i$时,构造$p = i*k + r$

    有$i*k+r \equiv 0(mod \ p)$

    两边同乘$i^{-1},r^{-1}$,得$k*r^{-1}+i^{-1} \equiv 0 (mod \ p)$

    移项,得$i^{-1} \equiv -k*r^{-1} (mod \ p)$

    由题意,得$k = \lfloor {p/i} \rfloor, r = p \ mod \ i$。

    代入,得$i^{-1} = - \lfloor p / i \rfloor * (p \ mod \ i) ^ {-1} $。

    现实使用中,我们常常会使用$(p - \lfloor p/i \rfloor)$来避免负数!

    由此式,即可线性递推逆元,也可以递归求解,将较大的数缩小到某个范围内

    PS:据说这种递归求解方式上界约为$O(n^{\frac{1}{3}})$?

  • 阶乘逆元

    如果只是某个阶乘,可以用上面递归的方式去做,如果是求一串阶乘(以$0!-n!$为例)的逆元,则:

    1. 先用某种方法求出$n!$的逆元

    2. 由$\frac{1}{(n+1)!} (n+1)=\frac{1}{n!}$,得$inv[n] = inv[n+1] (n+1)$。

      【因为逆元相当于求倒数,由此可以开始递推】

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define maxn 1000010
#define mod 1000000007
#define int long long
using namespace std;
int h[maxn], sum[maxn], ans[maxn], inv[maxn], cn[maxn], cm[maxn];
int qpow(int a, int b){
if(b == 1) return a;
int tmp = qpow(a, b / 2);
tmp = (tmp * tmp) % mod;
if(b & 1) tmp = (tmp * a) % mod;
return tmp;
}
int calc(int x){
if(x < maxn-10)
return inv[x];
return (calc(mod % x) * (mod - mod / x)) % mod;
}
int bin(int x, int y){
return (((cn[y] * cm[x]) % mod) * cm[y-x]) % mod;
}
signed main(void)
{
ans[1] = 1; inv[1] = 1;
h[0] = h[1] = 1;
sum[0] = 1; sum[1] = 2;

for(int i = 2; i <= 1000001; i++)
inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
cn[0] = cm[0] = 1;
for(int i = 1; i <= 1000000; i++)
{
h[i] = ((((4 * i - 2) * inv[i + 1]) % mod) * h[i - 1]) % mod;
cn[i] = (cn[i-1] * i) % mod;
//利用递推的思路求逆元
cm[i] = calc(cn[i]);
}
//阶乘求逆元独有
/*
cm[1000000] = qpow(cn[1000000], mod-2);
for(int i = 1000000-1; i >= 0; i--)
cm[i] = (cm[i + 1] * (i + 1)) % mod;
*/
int t, n;
scanf("%lld", &t);
while(t--)
{
scanf("%lld", &n);
if(ans[n])
{
printf("%lld\n", ans[n]);
continue;
}
for(int j = 0; j <= n / 2; j++)
ans[n] = (ans[n] + bin(2*j, n) * h[j]) % mod;
printf("%lld\n", ans[n]);
}
return 0;
}

HDU2999

SG函数入门题。

需要注意,取的是连续的某一段石头,不一定是在两端取。

因此,存在这一回合取完石头后分裂为两个局势的情况,此时就要使用$SG$定理进行解决。

一般来说,推导$SG$函数有两种方法,一个是由小到大,直接递推,另一个是首先$SG$函数值初始化为$-1$,每次使用$dfs$求解(记忆化,若SG不为$-1$则直接返回)。

这里使用的是递推的方法,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, k, a[maxn], se[maxn];
int s[maxn], sg[maxn];
//递推求解SG模板
void SG(){
memset(sg, 0, sizeof(sg));
for(int i = 1; i <= 1000; i++)
{
memset(s, 0, sizeof(s));
//se是已经有序的,因此可以这样子设置条件
for(int j = 1; se[j] <= i && j <= se[0]; j++)
{
//在边边取石头的情况
s[sg[i-se[j]]] = 1;
int tot = i - se[j];
//分裂为两个局势的情况
for(int k = 1; k <= tot - 1; k++)
s[sg[k]^sg[tot-k]] = 1;
}
//s用于判断是否出现过,再用这个循环做一遍mex
for(int j = 0; j <= 1000; j++)
{
if(!s[j])
{
sg[i] = j;
break;
}
}
}
}
int main(void)
{
while(~scanf("%d", &n))
{
se[0] = 0;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a+1, a+n+1);
//去重
for(int i = 1; i <= n; i++)
if(a[i] != a[i-1]) se[++se[0]] = a[i];
SG();
scanf("%d", &m);
for(int i = 1; i <= m; i++)
{
scanf("%d", &k);
printf(sg[k] ? "1" : "2");
putchar('\n');
}
}
return 0;
}

HDU1527

威佐夫博弈入门题。

经典情形:

  • 有两堆石头,两堆石头数目可以不同,每人轮流取石头
  • 可以选择一堆石头拿走任意个石头
  • 可以选择两堆石头拿走相同个石头
  • 谁最后拿完谁赢

然后,若两堆石头差的绝对值乘上(1+sqrt(5))向下取整后,等于两堆石头中较小那堆石头的数目,则为奇异局势。奇异局势先手则必输,反之必胜。

关于证明暂时鸽鸽了,实在比较难弄。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main(void)
{
while (~scanf("%lld %lld", &a, &b))
{
if(a > b) swap(a, b);
long long c = b - a;
long long ans = c * (1.0 + sqrt(5.0)) / 2;
printf("%lld\n", ans == a ? 0 : 1);
}
return 0;
}

如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ