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

· · 题解

为什么你们的方法都那么高端。。。好高大上，我这小白都看不懂，我感觉这道题就是一道高中的排列组合问题啊。

原理：

考虑黑色格子最多的情况：最左侧是黑色，然后每隔M个格子都是黑色，这种情况下的黑色格子的总数为：(N-1)/(M+1)+1 这种排列情况最右侧的无色格子为(N-1)%(M+1)，由于黑色格子间隔最少是M，并且此种情况所有黑色格子间隔都是M,所以黑色格子中间的格子是不能动的。现在把最右侧的无色格子看成是活动的，那么这些格子放置到任何位置都能满足要求，又因为(N-1)/(M+1)+1个黑色格子将N分割为了(N-1)/(M+1)+2个区域，所以黑色格子最多时的方案问题就转化为了高中的排列组合问题：(N-1)%(M+1)个小球放入(N-1)/(M+1)+2个盒子，小球相同，盒子不同，盒子里的小球可以为0。所以这种情况的方案数为C[((N-1)%(M+1)+(N-1)/(M+1)+1),(N-1)/(M+1)+1）。根据这种原理就可以求得所有的方案数了。代码如下：

// luogu-judger-enable-o2
#include<stdio.h>

long long factorial(int m, int n)
{
    int i,j;
    long long  ans = 1;
    if(m < n-m) m = n-m;
    for(i = m+1; i <= n; i++) ans *= i;
    for(j = 1; j <= n - m; j++) ans /= j;
    return ans;
}
int main()
{
int N,M,k,a,b,c=0;
long long d=0;
scanf("%d%d",&N,&M);
k=(N-1)/(M+1)+1;
a=(N-1)%(M+1);
for(b=k;b>1;b--)
{
  d += factorial(b,a+c*(M+1)+b);
  c++;
}
printf("%lld",(d+N+1)%1000000007);
return 0;
}

但是这个代码只能得10分，当N大的时候不行了，我是刚刚入门算法，所以也不会优化，还请大神们帮我优化一下，不过这个原理是没问题的