vs网站开发,中企动力企业邮箱入口,深圳英文网站建设专业公司,进入wordpress很慢正题
题目链接:https://www.luogu.org/problemnew/show/P5004 题目大意
把NNN个无色格子排成一行#xff0c;可以把某些格子染成黑色#xff0c;但两个黑色格子之间必须至少有MMM个无色格子#xff0c;求方案数 解题思路
首先很明显 fn∑i0n−m−1fif_n\sum_{i0}^{n-m-1}…正题
题目链接:https://www.luogu.org/problemnew/show/P5004 题目大意
把NNN个无色格子排成一行可以把某些格子染成黑色但两个黑色格子之间必须至少有MMM个无色格子求方案数 解题思路
首先很明显 fn∑i0n−m−1fif_n\sum_{i0}^{n-m-1}f_ifni0∑n−m−1fi
然后我们发现∑i0n−m−1fi\sum_{i0}^{n-m-1}f_i∑i0n−m−1fi就是前缀和那我们在矩阵乘法中维护一个前缀和 A[∑i0n−m−1fifn−mfn−m1...fn−1fn]A\begin{bmatrix}\sum_{i0}^{n-m-1}f_i \\ f_{n-m} \\ f_{n-m1} \\ ... \\ f_{n-1} \\ f_{n} \end{bmatrix}A⎣⎢⎢⎢⎢⎢⎢⎡∑i0n−m−1fifn−mfn−m1...fn−1fn⎦⎥⎥⎥⎥⎥⎥⎤ 然后看着转移就好了。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define ll long long
using namespace std;
const ll Size20,XJQ1e97;
struct matrix{ll a[Size][Size];
}f;
ll n,m;
matrix operator *(matrix a,matrix b)
{matrix c;memset(c.a,0,sizeof(c.a));for(ll i0;im;i)for(ll j0;jm;j)for(ll k0;km;k)(c.a[i][j]a.a[i][k]*b.a[k][j]%XJQ)%XJQ;return c;
}
matrix power(matrix f,ll b)
{b--;matrix ans;memset(ans.a,0,sizeof(ans.a));for(int i0;im;i)ans.a[0][i]1;ans.a[0][m];while(b){if(b1) ansans*f;ff*f;b1;}return ans;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;im;i)f.a[i][i-1]1;f.a[0][m]1;f.a[m][m]1;fpower(f,n);printf(%lld,f.a[0][m]);
}
