一、题意

求以x结尾的长度为l的不下降正整数数列一共有多少个。对911451407取模。
输入共有kase（kase<=1e5）组数据，每组数据满足x、l<=1e6。

二、解析

  • 这是一道数学类题目。一开始看到题目的第一直觉是用动态规划，即dp[l][x]表示以x为结尾的长度为l的不下降正整数数列个数。则由dp[l][x]=∑dp[l-1][1...x]。然而由于x、l<=1e6，我们第一没有足够的空间开数组，第二时间复杂度也一定为超时。

  • 于是我们考虑在一个x*l的平面上考虑递推式dp[l][x]=∑dp[l-1][1...x]的含义，即每一个（x,l）格子的数字等于它的左边一列的所有比它行数小或等于的格子的数字之和。也就是我们可以把递推式简化为dp[l][x]=dp[l-1][x]+dp[l][x-1]。这个递推式是不是很眼熟？它就是求从（0，0）到（x，l）格子的路径（只允许→、↓）数目的式子。而求解这个路径个数我们直接用数学方法可以求得，即C（x+l-2,x-1），就是从路径边中挑选一部分作为纵向边，每一次挑选就对应一条路径。

  • 既然知道了问题的答案就是C（x+l-2,x-1），接下来就是如何求解的问题。由于答案需要取模，因此求解过程中会遇到除法取模的情形，这时就需要用到费马小定理来将除法取模转化为乘以原数的逆元，设这个除数为b，则它的逆元根据费马小定理就是b^(mod-2)。b、mod需要互质。

  • 而求解b^(mod-2)也需要一个快速算法，否则会超时，这个算法就是快速幂算法。

  • 快速幂算法：一种用来快速求解指数很大的幂运算的算法。原理是将幂次减半，底数平方，并以此类推直到幂次为0。比如3^10=9^5=(9^4)(9^1)=(81^2)(9^1)=(6561^1)(9^1)，这样原式的答案就是6561*9了。

  • 另外，注意到题目kase值会很大，一般这种时候要考虑在进入输入前进行打表初始化，从而加快效率。

三、代码

#include <iostream>
using namespace std;
using LL = long long;
const int mod = 911451407;
const int maxn = 2e6 + 5;
int kase, l, x;
LL fac[maxn], inv_fac[maxn];

LL fast_pow_mod(LL a, LL b) {  // 快速幂算法 带mod版
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res % mod;
}

void init(int n) {  // 打表初始化 阶乘fac[maxn] 和 阶乘的逆元inv_fac[maxn]
    fac[0] = inv_fac[0] = 1;
    for(int i = 1; i <= n; i ++) {
        fac[i] = fac[i - 1] * i % mod;
        inv_fac[i] = fast_pow_mod(fac[i], mod - 2);
    }
}

int C(int n, int m) {  // 答案就是一个组合数，用费马小定理求组合数的模
    return fac[n] * inv_fac[n - m] % mod * inv_fac[m] % mod;
}

int main() {
    cin >> kase;
    init(maxn - 1);
    while(kase --) {
        cin >> l >> x;
        cout << C(l + x - 2, l - 1) << endl;
    }
}

四、归纳

  • 当看到连动态规划都会超时的题目时，很有可能要用到数学方法。
  • 求带模的组合数时，由于涉及到除法取模，因此需要使用费马小定理将除法取模转化为乘法取模： 
int C(int n, int m) {  // n! / (n-m)! / m! => n! * [(n-m)!]^(mod-2) * [m!]^(mod-2)
    return fac[n] * inv_fac[n - m] % mod * inv_fac[m] % mod;
}
  • 快速幂算法，用于快速求解指数很大的幂运算，注意用long long： 
LL fast_pow_mod(LL a, LL b) {  // 快速幂算法 带mod版
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;  // 指数为奇时分一个出来
        b >>= 1;  // 指数减半
        a = a * a % mod;  // 底数平方
    }
    return res % mod;
}