Page 2 of 2

### Beautiful proof

Posted: Sat Jan 01, 2005 5:25 am
Really nice proof. Thanks for it.

Posted: Sat Jan 01, 2005 6:52 am
Hi Cho, I am really interesed about your proof, but unfortunately I can't open the file format you have used. do you have any other file format like .pdf or plz mention what software will support the file, I will collect it then.

Posted: Sat Jan 01, 2005 8:04 am

Posted: Sat Jan 01, 2005 8:47 am
CodeMaker wrote:do you have any other file format like .pdf
here is the pdf format: 10743.pdf

### Re: 10743 - Blocks on Blocks

Posted: Sat Aug 14, 2010 2:11 am
hi alll ....
can somebody help
it doesnt work for n==999 ... returns negative number .....
why???????!!!!!!

Code: Select all

#include<iostream>
using namespace std;
const long long Mode=10000;
#define FOR(i,n) for(int i=0;i<n;++i)
long long matrix[3][3]={0,0,4,1,0,-7,0,1,5},result[3][3],temp[3][3];
void power(int n ){
if(n==1) FOR(r,3)FOR(c,3)result[r][c]=matrix[r][c];
else if(n%2==1){
power(n/2);
FOR(r,3)FOR(c,3)temp[r][c]=0;
FOR(r,3)FOR(c,3)FOR(i,3)temp[r][c] = (temp[r][c]+result[r][i]*result[i][c])%Mode ;

FOR(r,3)FOR(c,3)result[r][c]=0;
FOR(r,3)FOR(c,3)FOR(i,3)result[r][c] = (result[r][c] + temp[r][i]*matrix[i][c])%Mode;
}
else {
power(n/2);
FOR(r,3)FOR(c,3)temp[r][c]=0;
FOR(r,3)FOR(c,3)FOR(i,3)temp[r][c] = (temp[r][c] + result[r][i]*result[i][c] )%Mode;

FOR(r,3)FOR(c,3)result[r][c]=temp[r][c];
}
return ;
}
int main(){
//freopen("in.txt","r",stdin);
int cas,n,res;
scanf("%d",&cas);
for(int ca=0;ca<cas;++ca){
scanf("%d",&n);
if(n==1)res=1;
else if(n==2)res=2;
else if(n==3)res=6;
else if(n==4)res=19;
else {
power(n-4);
res= ( result[0][2]*2 + result[1][2]*6 + result[2][2]*19 )%Mode;
}
if(n<9)printf("Case %d: %d\n",ca+1,res);
else printf("Case %d: %04d\n",ca+1,res);
}
return 0;
}

### Re: 10743 - Blocks on Blocks

Posted: Wed Nov 16, 2016 2:56 am
Ok, from Cho's hints I've been able to go as far as this:

a_n = \sum_{k=1}^{n}b_{n,k},
b_{n,k} = \sum_{t=1}^{n-k}(t+k-1)b_{n-k,t}

I can take this one step further, but how to get to the formula a_n = ?a_{n-1} + ?a_{n-2} + ?a_{n-3}?
Cho's derivation is no longer accessible.