[BZOJ4870][Shoi2017]組合數問題（矩陣乘法）

數學真可怕。

Source

https://www.lydsy.com/JudgeOnline/problem.php?id=4870

Solution

首先，組合數有一個重要的性質：

Cmn=Cmn−1+Cm−1n−1 C n m = C n − 1 m + C n − 1 m − 1

設：

f(m,r)=∑i=0∞Cik+rm f ( m , r ) = ∑ i = 0 ∞ C m i k + r

根據組合數的性質推出：

f(m,r)=∑i=0∞(Cik+rm−1+Cik+(r+k−1)modkm−1) f ( m , r ) = ∑ i = 0 ∞ ( C m − 1 i k + r + C m − 1 i k + ( r + k − 1 ) mod k )

=∑i=0∞Cik+rm−1+∑i=0∞Cik+(r+k−1)modkm−1 = ∑ i = 0 ∞ C m − 1 i k + r + ∑ i = 0 ∞ C m − 1 i k + ( r + k − 1 ) mod k

=f(m−1,r)+f(m−1,(r+k−1)modk) = f ( m − 1 , r ) + f ( m − 1 , ( r + k − 1 ) mod k )

邊界 f(0,0)=1 f ( 0 , 0 ) = 1 。

由于 k k <script type="math/tex" id="MathJax-Element-7">k</script> 不大，是以用矩陣乘法就能解決這個問題。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std; typedef long long ll;
const int N = ;
int n, PYZ, k, r;
struct cyx {
    int n, m, a[N][N]; cyx() {} cyx(int _n, int _m) : n(_n), m(_m)
        {memset(a, , sizeof(a));}
    friend inline cyx operator * (const cyx &a, const cyx &b) {
        int i, j, k; cyx res = cyx(a.n, b.m);
        For (i, , res.n) For (j, , res.m) For (k, , a.m)
            res.a[i][j] = (res.a[i][j] + l * a.a[i][k] * b.a[k][j] % PYZ) % PYZ;
        return res;
    }
    friend inline cyx operator ^ (cyx a, ll b) {
        int i; cyx res = cyx(a.n, a.m); For (i, , res.n) res.a[i][i] = ;
        while (b) {
            if (b & ) res = res * a; a = a * a; b >>= ;
        }
        return res;
    }
} P, Y, Z;
int main() {
    int i; cin >> n >> PYZ >> k >> r; P = cyx(k, k);
    For (i, , k - ) P.a[i + ][i + ]++, P.a[i + ][(i + k - ) % k + ]++;
    Y = cyx(, k); Y.a[][] = ; Z = Y * (P ^ l * n * k);
    cout << Z.a[][r + ] << endl; return ;
}