2014
02-23

I Speak Whales

According to Wikipedia, a Walsh matrix is a specific square matrix, with dimensions equal to a power of 2, the entries of which are +1 or -1, and the property that the dot product of any two distinct rows (or columns) is zero. Below are the first three Walsh Matrices. (The gray lines are imaginary lines for illustration purpose only.)

A Walsh Matrix of size 2N+1 can be constructed as the “union” of 4 Walsh Matrices of size 2N arranged such that the lower right matrix is inverted whereas the other 3 matrices are not, i.e.:

Let’s number the rows of a given Walsh Matrix from the top starting with row 0. Similarly, let’s number the columns of the matrix from the left starting with column 0. Given the four integers N , R , S , and E , write a program that will construct a Walsh Matrix of size 2N and will print the sum of all the numbers in row #R between columns #S and #E (inclusive.)

Your program will be tested on one or more test cases. Each test case is specified using a single line listing four integers in the following order: N , R , S , and E , where 0<=N<=60 , 0<=R < 2^N , 0<=S<=E < 2^N , and E-S<=10, 000 . The last line of the input file has four -1′s and is not part of the test cases.

Your program will be tested on one or more test cases. Each test case is specified using a single line listing four integers in the following order: N , R , S , and E , where 0<=N<=60 , 0<=R < 2^N , 0<=S<=E < 2^N , and E-S<=10, 000 . The last line of the input file has four -1′s and is not part of the test cases.

2 1 0 1
48 0 0 47
-1 -1 -1 -1

0
48

AC代码：

#include<stdio.h>
#include<string.h>
__int64 f[70];
__int64 work(int n,__int64 r,__int64 st,__int64 ed)
{
__int64 sum=0,num;
if(n==0)return 1;
num=f[n]/2;
if(r<=num){
if(ed<=num){
sum=work(n-1,r,st,ed);
}else if(st>num){
sum=work(n-1,r,st-num,ed-num);
}else {
sum=work(n-1,r,st,num);
sum+=work(n-1,r,1,ed-num);
}
}else{
if(ed<=num){
sum=work(n-1,r-num,st,ed);
}else if(st>num){
sum=-work(n-1,r-num,st-num,ed-num);
}else {
sum=work(n-1,r-num,st,num);
sum-=work(n-1,r-num,1,ed-num);
}
}
return sum;
}
int main()
{
int i,j;
int n;
__int64 r,st,ed,ans;
f[0]=1;
for(i=1;i<=60;i++){
f[i]=f[i-1]*2;
}
while(scanf("%d%I64d%I64d%I64d",&n,&r,&st,&ed)){
if(n==-1&&r==-1&&st==-1&&ed==-1)break;
ans=work(n,r+1,st+1,ed+1);
printf("%I64d\n",ans);
}
return 0;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1