Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems 矩阵优化

题解

题目大意，问单个的1与长度为m的0能组成多少个长度为n的序列，1和0有无限多个。

暴力打表发现当m等于2时候与斐波那契数列相同，其它情况为f[n] = f[n - 1] + f[n - m]，递推式很简单但是n很大直接递推超时。
使用矩阵优化进行转移复杂度O(m^3*logn)

AC代码

#include <stdio.h>
#include <bits/stdc++.h>
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAXN = 110;

struct Matrix
{
	ll m[MAXN][MAXN];
	const static int N = 100; //阶数
	Matrix(ll v = 0)
	{
		memset(m, 0, sizeof(m));
		if (v)
			for (int i = 0; i < N; i++)
				m[i][i] = v;
	}
	Matrix operator * (const Matrix &b)
	{
		Matrix t;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					t.m[i][j] = (t.m[i][j] + m[i][k] * b.m[k][j]) % MOD;
		return t;
	}
	friend Matrix operator ^ (Matrix a, ll n)
	{
		Matrix t(1);
		while (n)
		{
			if (n & 1)
				t = t * a;
			a = a * a;
			n >>= 1;
		}
		return t;
	}
}a, tran;
int main()
{
#ifdef LOCAL
	//freopen("C:/input.txt", "r", stdin);
#endif
	ll n, m;
	cin >> n >> m;
	if (n < m)
		cout << 1 << endl, exit(0);
	a.m[0][0] = 1; //f[0]=a.m[0][0]=0, f[-1]=a.m[0][1]...
	for (int i = 0; i < m; i++)
		tran.m[i][i + 1] = 1; //每一项都转移到下一项 因为*tran之后后推了一次
	tran.m[0][0] = tran.m[m - 1][0] = 1; //新的项由前1项和前第m项转移 后推再-1
	a = a * (tran ^ n);
	cout << a.m[0][0] << endl;

	return 0;
}