プロジェクトオイラー問294 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20294

0<k<10^(11^12)な数ｋのうち、２３で割り切れてかつ各桁の和が23になるｋの数を答えよ。
答えは10＾9で割った余りで答えよ。
計算時間３秒の解。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>

const int LIMIT=23;
const int LIMIT1=24;
const __int64 MOD=10000*10000*10;
const __int64 U=pow(11,6);
__int64 up=U*U;
__int64 mult;

void f(__int64 a[LIMIT1][LIMIT],__int64 b[LIMIT1][LIMIT],__int64 c[LIMIT1][LIMIT],int n,bool t){
	memset(c,0,LIMIT*LIMIT1*8);
	//a[桁和][２３の倍数か]
	for(int i=0;i<=LIMIT;i++){
		//桁和
		for(int j=0;j<=i;j++){
			int p1=j;
			int p2=i-j;
			for(int k=0;k<LIMIT;k++){
				int p3=k;
				for(int l=0;l<LIMIT;l++){
					int p4;
					if(t==true){
						p4=(l*mult)%LIMIT;
					}else{
						p4=(l*n)%LIMIT;
					}
					c[i][(p3+p4)%LIMIT]=(c[i][(p3+p4)%LIMIT]+(a[p2][l]*b[p1][k]))%MOD;
				}
			}
		}
	}
	if(t==true){
		mult=(mult*n)%LIMIT;
	}
} 

int main(){
	__int64 a[LIMIT1][LIMIT];//a[桁和][２３の倍数か]
	__int64 ans[LIMIT1][LIMIT],c[LIMIT1][LIMIT];

	memset(a,0,sizeof(a));

	for(int i=0;i<=9;i++)a[i][i]=1;

	bool isF=true;
	mult=10;
	int n=mult;
	while(up>0){
		if(up%2==1){
			if(isF==false){
				f(a,ans,c,n,true);
				memcpy(ans,c,sizeof(ans));
			}else{
				isF=false;
				memcpy(ans,a,sizeof(a));
			}
		}
		f(a,a,c,n,false);
		memcpy(a,c,sizeof(c));
		up/=2;
		n=(n*n)%LIMIT;
	}
	std::cout<<ans[23][0]<<"\n";
}