传送门: https://www.luogu.org/problemnew/show/P5004
分析
动态规划转移方程是这样的 \(f[i]=\sum^{i-m-1}_{j=0}f[j]\).
那么很明显的是要构造举证, 而且要维护前缀和, 所以需要保留 \(m+1\) 项.
ac 代码
- #include <bits/stdc++.h>
- #define ll long long
- #define ms(a, b) memset(a, b, sizeof(a))
- #define inf 0x3f3f3f3f
- #define N 25
- #define mod ((int)1e9 + 7)
- using namespace std;
- template <typename T>
- inline void read(T &x) {
- x = 0; T fl = 1;
- char ch = 0;
- while (ch <'0' || ch> '9') {
- if (ch == '-') fl = -1;
- ch = getchar();
- }
- while (ch>= '0' && ch <= '9') {
- x = (x <<1) + (x << 3) + (ch ^ 48);
- ch = getchar();
- }
- x *= fl;
- }
- ll n;
- int m;
- struct Matrix {
- int a[N][N], x, y;
- void init() {
- memset(a, 0, sizeof(a));
- x = y = 0;
- }
- Matrix operator *(const Matrix &rhs) const{
- Matrix res; res.init();
- res.x = x, res.y = rhs.y;
- int c = y;
- for (int i = 1; i <= x; i ++) {
- for (int j = 1; j <= y; j ++) {
- for (int k = 1; k <= c; k ++) {
- res.a[i][j] = (res.a[i][j] + (ll) a[i][k] * rhs.a[k][j]) % mod;
- }
- }
- }
- return res;
- }
- Matrix power(Matrix a, ll b) {
- Matrix res;
- res.init();
- res.x = res.y = a.x;
- for (int i = 1; i <= res.x; i ++) res.a[i][i] = 1;
- for (; b; b>>= 1) {
- if (b & 1) res = res * a;
- a = a * a;
- }
- return res;
- }
- }a, b;
- int main() {
- read(n); read(m);
- if (n <= m) {
- printf("%lld\n", n + 1);
- return 0;
- }
- a.x = a.y = m + 2, b.x = m + 2, b.y = 1;
- for (int i = 2; i <= m + 2; i ++)
- b.a[i][1] = 1;
- b.a[1][1] = m + 1;
- a.a[1][1] = a.a[1][2] = 1;
- a.a[2][2] = a.a[2][m + 2] = 1;
- for (int i = 3; i <= m + 2; i ++) a.a[i][i - 1] = 1;
- a = a.power(a, n - m);
- b = a * b;
- printf("%d\n", b.a[1][1]);
- return 0;
- }
[luogu5004] 专心 OI - 跳房子
来源: http://www.bubuko.com/infodetail-2994201.html