自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:06:05，当前版本为作者最后更新于2018-11-05 13:21:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

PS:本题目题解涉及到的矩阵表示方法可能有点问题……凑和着看吧

本题受 [SCOI2005]互不侵犯启发而出

题目简化一下……把$N$个无色格子排成一行，可以把某些格子染成黑色，但两个黑色格子之间必须至少有$M$个无色格子

题目没出$M=0$因为这样就成了快速幂了，但是……$STD$还是快速幂

$10pts$ dfs爆搜

#include<iostream>
#include<cstdio>
#define max(a,b) (a>b?a:b)
long long n,m;
#define mod (1000000007)
int cnt;
void dfs(int now){
    if(now>n){
        if(cnt==mod)	cnt=0;
        ++cnt;
        return;
    }
    if(now+m+1>n){
        if(cnt==mod)	cnt=0;
        ++cnt;
        return ;
    }
    for(register int i=max(1,now+1+m);i<=n+1;++i)
        dfs(i);
}

int main(){
    scanf("%lld%lld",&n,&m);
    dfs(-20);
    printf("%d",cnt);
    return 0;
}

顺带收获$TLE*8,MLE*10$

这是找规律好题鸭！

$20pts$ 考虑$M=1,N<=10^7$

$N$	$ANS$
$1$	$2$
$2$	$3$
$3$	$5$
$4$	$8$
$5$	$13$

是否发现什么奥秘？

然而就是斐波那契数列……

    scanf("%lld%lld",&n,&m);
    long long a=2,b=3,c=0;
    for(register int i=1;i<n;++i){
    	c=a+b;
    	c%=mod;
    	a=b,b=c;
    }
    printf("%lld",a);

这20分爽吧

$30pts$ 矩阵优化一波

这样应该可以过$M=1$的所有数据啦

不会矩阵乘法？洛谷有优质的模板1，模板2去看题解吧！

$50pts$ 让我们继续找规律

再看看$M=2$

$N$	$ANS$
$1$	$2$
$2$	$3$
$3$	$4$
$4$	$6$
$5$	$9$

您可以发现前$3$项值都是$N+1$ 之后$ANS_i=ANS_{i-1}+ANS_{i-3}$

好玩吧？

您也可以自己寻找$M=3$ 的规律,不过我在这里给出结论

$\begin{cases} S_i=i+1,~~~~i\in[1,M+1] \\ S_i=S_{i-1}+S_{i-1-M},~~~~i\in[M+2,\infty] \end{cases} $

不知道这些数学符号对不对呀…………我只是个初中生

（如果您是递归做的只有$45pts$,因为会$MLE$）

$100pts$ 继续矩阵优化

矩阵的大小和数值随$M$变化

原矩阵为

$\begin{matrix} ANS_1~~~ANS_2~...~ANS_{M+1} \end{matrix}$

乘一遍矩阵应该变成

$\begin{matrix} ANS_2~~~ANS_3~...~ANS_{M+2} \end{matrix}$

下面讨论用来乘的矩阵

可以发现$M=1$时，矩阵应该为

$\begin{matrix} 0~~~~1\\1 ~~~~1 \end{matrix}$

$M=2$时，矩阵为

$\begin{matrix} 0~~~~0~~~~1\\1 ~~~~0~~~~0\\0~~~~1~~~~1 \end{matrix}$

$M=3$时，矩阵为

$\begin{matrix} 0~~~~0~~~~0~~~~1\\1 ~~~~0~~~~0~~~~0\\0~~~~1~~~~0~~~~0\\0~~~~0~~~~1~~~~1 \end{matrix}$

$M=4$时，矩阵为

$\begin{matrix} 0~~~~0~~~~0~~~~0~~~~1\\1 ~~~~0~~~~0~~~~0~~~~0\\0~~~~1~~~~0~~~~0~~~~0\\0~~~~0~~~~1~~~~0~~~~0\\0~~~~0~~~~0~~~~1~~~~1 \end{matrix}$

规律很明显了

这个斜率为$-1$的长条上都是$1$，最后一列第一个和最后一个是$1$除此之外都是$0$,如此构造矩阵即可！

您也许可以写个dp，但是不知道多少分

然后搞矩阵快速幂即可