NC-C11170-C 不降数

背景

一次牛客练习赛的题目,赛时直接$OEIS$加$Lucas$定理搞过去了,赛后发现其实矩阵快速幂递推的方法更好理解,记录一下两种写法(以及出题人的题解感觉有点不讲人话)

题解

首先标一下出题人的题解,不过有一说一,没有明白啥是统计差分序列的数量。如果有大佬知道可以在评论区告诉小萌新嘛U•ェ•*U

image-20210411162703897


然后考虑打表的写法,$OEIS$可以通过前三项$(9,45,165)$得到$ans = \tbinom{n + 8}{8}$的规律,观察到$n$比较大,$p$比较小,只需要套一个$Lucas$定理的模板即可。

模板来源:xienaoban

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
typedef long long lld;

lld pow_mod(lld a, lld b, const int &pr)
{
lld ans = 1;
while (b) {
if (b & 1) ans = ans * a % pr;
b >>= 1;
a = a * a % pr;
}
return ans;
}

lld C_small(lld n, lld m, const int &pr)
{
lld ans = 1;
for (int i = 1; i <= m; i++)
{
lld a = (n - m + i) % pr;
lld b = i % pr;
ans = ans * (a * pow_mod(b, pr - 2, pr) % pr) % pr; //Fermat Theory
}
return ans;
}

lld C(lld n, lld m, const int &pr) // Lucas's theorem
{
if (m == 0 || m == n) return 1;
return C_small(n % pr, m % pr, pr) * C(n / pr, m / pr, pr) % pr;
}

那么怎么去解释这个$\tbinom{n+8}{8}$呢,我队友给出了一个他的看法:

对于$\tbinom{n+8}{8}$,可以看成$\tbinom{n+8}{n}$,也就是我们在$n+8$个数字中选择$n$个数字。

当$n=1$时,即在$9$个数字中取$1$个,答案为$9$。

当$n=2$时,要在$10$个数字中取$2$个,这$10$个数字里,包含了出现重复数字$k$的情况。

比如$1,2,3,4,5,6,7,8,9,2$,出现了两次$2$,包含了选择两次$2$的情况。

然后,对于选择其中任意的两个数,都有且仅有一种排列方式,能够使得组成的序列是不降的。

因此,可以使用这种方式来表示答案。

(不过这里只是感性理解,不知道怎么严格证明,可能会有纰漏)


过了两天,返回题解区,发现原来可以用矩阵快速幂的方法来做。

当晚我们推出了一个转移方程:

$$dp[i][j] = \sum_{k=1}^{j} dp[i - 1][k]$$

但是我们发现这个运算量大概要去到$100 * 10^8$左右,是很难过得去这题的,于是就搁置了。

不过如果转成矩阵,就很好做了。

便于演示,我们假定只有$1,2,3$三种数字可以选择。

image-20210411171121502


由上,我们可以推广到九个数的情况,设置一个$9*9$的矩阵用于转移,进行矩阵快速幂即可。

代码如下:

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
#include <bits/stdc++.h>
#define maxn 15
#define mod 100019
#define int long long
using namespace std;
int n;
struct Matrix{
int M[maxn][maxn];
}I, B;
Matrix operator * (const Matrix &A, const Matrix &B){
Matrix res;
memset(res.M, 0, sizeof(res.M));
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
for(int k = 1; k <= 9; k++)
res.M[i][j] = (res.M[i][j] + A.M[i][k] * B.M[k][j]) % mod;
return res;
}
Matrix quickpow(Matrix a, int b){
if(b == 0) return I;
Matrix tmp = quickpow(a, b / 2);
tmp = (tmp * tmp);
if(b & 1) tmp = (tmp * a);
return tmp;
}
void init(){
for(int i = 1; i <= 9; i++) I.M[i][i] = 1;
for(int i = 1; i <= 9; i++)
for(int j = i; j <= 9; j++)
B.M[i][j] = 1;
}
void Print(Matrix now){
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
printf(j == 9 ? "%d\n" : "%d ", now.M[i][j]);
}
signed main(void)
{
init();
scanf("%lld", &n);
Matrix res = quickpow(B, n - 1);
int ans = 0;
for(int i = 1; i <= 9; i++)
for(int j = i; j <= 9; j++)
ans = (ans + res.M[i][j]) % mod;
Print(res);
printf("%lld\n", ans);
return 0;
}

后来,评论区有人提到:递推100019次,而且还是一个和式,那么一定是100019的倍数!

因此,可以将$n \ mod \ 100019$,再进行递推,这样复杂度是符合题意的。

别的

总的来说这题还是蛮快乐的,复习了一下矩阵快速幂U•ェ•*U

想每日培养好习惯却天天鸽鸽,有点麻(