背景

一次牛客练习赛的题目，赛时直接$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$的情况。

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

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

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

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

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

但是我们发现这个运算量大概要去到$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

想每日培养好习惯却天天鸽鸽，有点麻（