Description FJ想N头牛（公牛或母牛）排成一排接受胡总的检阅，经研究发现公牛特别好斗，如果两头公牛离得太近就会发生冲突，通过观察两头公牛之间至少要有K(0<=K<=N)头母牛才能避免冲突。 FJ想请你帮忙计算一共有多少种放置方法，注意所有的公牛被认为是一样的，母牛也是，所以两种放置方法被认为不同当且仅当某些位置牛的种类不同。 Input 第一行：两个空格隔开的整数N（N<=100000）和K。 Output 输出一个整数表示方法总数，答案可能很大，所以只需输出mod 5,000,011的值即可。 Sample Input 4 2 Sample Output 6 Data Constraint Hint 【样例说明】 以下为6种放置方法，‘B’表示公牛，‘C’表示母牛 CCCC BCCC CBCC CCBC CCCB BCCB
//written by zzy
求有多少种放置方法，使两头公牛间至少有 K K K头母牛。
dp,设 f [ i , 0 ] f~[i,0]~ f [i,0] 表第i头放母牛的方案数 f [ i , 1 ] f~[i,1]~ f [i,1] 表第i头放公牛的方案数 易推 f [ i , 0 ] f~[i,0]~ f [i,0] = f [ i − 1 , 0 ] f~[i-1,0]~ f [i−1,0] + f [ i − 1 , 1 ] f~[i-1,1]~ f [i−1,1] //如果放母牛，上一个公母都可以。 f [ i , 1 ] f~[i,1]~ f [i,1] = f [ i − k − 1 , 0 ] f~[i-k-1,0]~ f [i−k−1,0] + f [ i − k − 1 , 1 ] f~[i-k-1,1]~ f [i−k−1,1] //如果放公牛，上一个公牛必须放 i − k − 1 i-k-1 i−k−1格前 答案为 f [ n , 0 ] + f [ n , 1 ] f[n,0]+f[n,1] f[n,0]+f[n,1]
#include<iostream> #include<cstdio> #include<algorithm> #define N 100005 #define Mod 5000011 using namespace std; int i,j,n,m,k; int f[N][2]; int main() { scanf("%d%d",&n,&k); f[1][1]=1; f[1][0]=1; for (i=2;i<=k+1;i++) f[i][1]=1,f[i][0]=(f[i-1][0]+f[i-1][1])%Mod; for (i=k+2;i<=n;i++) { f[i][0]=(f[i-1][0]+f[i-1][1])%Mod; f[i][1]=(f[i-k-1][1]+f[i-k-1][0])%Mod; } printf("%d",(f[n][0]+f[n][1])%Mod); }