题解 P5004 【专心OI - 跳房子】

· · 题解

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} $\begin{matrix} 0~~~~0~~~~1\\1 ~~~~0~~~~0\\0~~~~1~~~~1 \end{matrix} $\begin{matrix} 0~~~~0~~~~0~~~~1\\1 ~~~~0~~~~0~~~~0\\0~~~~1~~~~0~~~~0\\0~~~~0~~~~1~~~~1 \end{matrix} $\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，但是不知道多少分

然后搞矩阵快速幂即可