10743 - Blocks on Blocks

[ranjit]

Really nice proof. Thanks for it.

[CodeMaker]

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.

[..]

http://www.cs.wisc.edu/~ghost/

[Cho]

do you have any other file format like .pdf

here is the pdf format: 10743.pdf

[Angeh]

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;
}

[dull_jester]

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.