做一件代发的网站,哈尔滨app网站开发,常州制作企业网站,网站做代码图像显示不出来的正题
题目链接: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]);
}
