bzoj 4870: [Shoi2017]组合数问题

题意：

原体面很清楚了吧

题解：

一开始推了很久柿子，什么都没搞出来，完全没往dp那边想。。
考虑这个柿子的意义：$nk$个物品中选$x$个的方案数，其中$x \equiv r \pmod k$。设$f_{i, j}$表示前$i$个选$x$个的方案数（$x \equiv j \pmod k$），$$
f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j}

$$
然后矩乘就好了。

#include <bits/stdc++.h>
using namespace std;

int n, p, k, r;
struct matrix
{
    int x, y;
    long long a[60][60];
    matrix()
    {
        memset(a, 0, sizeof(a));
    }
    long long *operator[](int x)
    {
        return a[x];
    }
} one, a, base;
matrix operator*(matrix x, matrix y)
{
    matrix ans;
    ans.x = x.x;
    ans.y = y.y;
    for (int i = 0; i < x.x; i++)
        for (int j = 0; j < y.y; j++)
            for (int k = 0; k < x.y; k++)
                (ans[i][j] += x[i][k] * y[k][j]) %= p;
    return ans;
}

matrix Pow(matrix x, long long y)
{
    if (y == 0) return one;
    matrix ans = Pow(x, y >> 1);
    ans = ans * ans;
    if (y & 1) ans = ans * x;
    return ans;
}
int main()
{
    // freopen("4870.in", "r", stdin);
    // freopen("4870.out", "w", stdout);
    scanf("%d%d%d%d", &n, &p, &k, &r);
    one.x = one.y = k;
    for (int i = 0; i < k; i++)
        one[i][i] = 1;
    a.x = 1;
    a.y = k;
    a[0][0] = 1;
    base.x = base.y = k;
    for (int i = 0; i < k; i++)
    {
        base[i][i]++;
        base[(i - 1 + k) % k][i]++;
    }
    /*
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
            printf("%lld ", base[i][j]);
        puts("");
    }*/
    a = a * Pow(base, 1LL * n * k);
    printf("%lld\n", a[0][r]);/*
    for (int i = 0; i < k; i++)
        printf("%lld ", a[0][r]);
    puts("");*/
}