题目：
Consider a code string S of N symbols, each symbol can only be 0 or 1. In any consecutive substring of S, the number of 0's differs from the number of 1's by at most K. How many such valid code strings S are there?
For example, when N is 4, and K is 3, there are two invalid codes: 0000 and 1111.
Input
The input consists of several test cases. For each case, there are two positive integers N and K in a line.
N is in the range of [1, 62].
K is in the range of [2, 5].
Output
Output the number of valid code strings in a line for each case.
Sample Input
1 2 4 3
Sample Output
2 14 中文解释：有个字符串由N个符号组成。每个符号只能是0或1,0和1的个数差不超过K,问满足条件的串有多少个？
例如，N=4, K=3
从0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 总的16种不同排列
0000 的0和1 相差4 1111 的0和1相差4 其他的最多相差2 所以答案14
解答：
基本思路：比如
N = 4;
K = 3;
L0是两个零，两个一的情况，那么字符串的个数为：
L0 = 4!/(2!*2!)=6 （0011 0101 1001 0110 1010 1100）
L1 不可能
L1 = 0
L2是一个零＋三个一，和三个零＋一个一
L2 = 4!/(3!*1!) * 2 = 8
L3不可能
L3 = 0
编程序一直到L5就行了。
L = L0＋L1+L2+L3 = 6+0+8+0=14
代码如下：(这个程序N不能超过13，因为int的限制)
#include <stdio.h>
int Odd(int s);
int L0(int n);
int L1(int n);
int L2(int n);
int L3(int n);
int L4(int n);
int L5(int n);
int factorial(int m);
int main()
{
int N,K;
int rslt = 0;
printf("please input the number of string : ");
scanf("%d",&N);
printf("please input the diference of string : ");
scanf("%d",&K);
switch(K){
case 2:
rslt = L0(N) + (L1(N) + L2(N)) * 2;
break;
case 3:
rslt = L0(N) + (L1(N) + L2(N) + L3(N)) * 2;
break;
case 4:
rslt = L0(N) + (L1(N) + L2(N) + L3(N) + L4(N)) * 2;
break;
case 5:
rslt = L0(N) + (L1(N) + L2(N) + L3(N) + L4(N) + L5(N)) * 2;
break;
}
printf("result = %d/n",rslt);
}int Odd(int s)//判断奇偶数
{
if(s % 2 == 0)
return 0;
else
return 1;
}
int L0(int n)//0和1的个数差为0
{
if(Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2) * factorial(n/2));
}
int L2(int n)//0和1的个数差为2
{
if(Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2+1) * factorial(n/2-1));
}
int L4(int n)//0和1的个数差为4
{
if(Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2+2) * factorial(n/2-2));
}
int L1(int n)//0和1的个数差为1
{
if(!Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2+1) * factorial(n/2));
}
int L3(int n)//0和1的个数差为3
{
if(!Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2+2) * factorial(n/2-1));
}
int L5(int n)//0和1的个数差为5
{
if(!Odd(n))
return 0;
else
return factorial(n) / (factorial(n/2+3) * factorial(n/2-2));
}
int factorial(int m)//求m的阶乘
{
int ret = 1;
while(m > 0)
{
ret = ret * m;
m--;
}
return ret;
}
程序2：(这个程序没有溢出的问题，不过没看明白)
#include <iostream>
using namespace std;static int c[ 63 ];
static int t[ 63 ];
static int temp[ 63 ];
int n, k;int main( void ) {
cin >> n >> k;
t[ 0 ] = 2;
t[ 2 ] = 2;
c[ 0 ] = 2;
c[ 2 ] = 2;
for( int i = 3; i <= n; i++ ) {
for( int j = 1; j <= i; j++ ) {
temp[ j ] = t[ j - 1 ] + t[ j + 1 ];
}
temp[ 1 ] += t[ 0 ];
temp[ 0 ] = t[ 1 ];
temp[ i ] = t[ i - 1];
memcpy( c, temp, 4 * ( n + 1 ) );
memcpy( t, temp, 4 * ( n + 1 ) );
memset( temp, 0, 4 * ( n + 1 ) );
}
unsigned long sum = 0;
for( i = 0; i <= k; i++ ) {
sum += c[ i ];
}
cout << "total:" << sum << endl;
return 0;
}