プロジェクトオイラー問217 Balanced Numbers

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20217
４７桁までのバランスのとれた整数全ての合計を3^15で割った余りでこたえる問題。
バランスのとれた数とは数字を真ん中で左右に区切って左と右別々に各桁の和をとった時、両側の合計が同じになる数のことである。
奇数桁の場合真ん中は無視してもよいようだ。


たぶん数式で求めるのだと思いますが私は数学の知識が乏しいので動的計画法で解きました。
意外と考えるパターンや桁あふれが多く結構苦労しました。
パズルゲームみたいで解いてて楽しい問題でした。


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

const int T=47;
const int LIMIT=T*9+10;
__int64 dp[T][LIMIT],permDP[T][LIMIT];



int main(){
      __int64 ans=45,temp,m=10,mR=1;
      __int64 MOD=pow(3,15);
      memset(dp,0,sizeof(dp));
      memset(permDP,0,sizeof(permDP));
      for(int i=1;i<10;i++){
            dp[0][i]=i;
            dp[T-1][i]=i;
            permDP[0][i]=1;
            permDP[T-1][i]=1;
      }
      for(int i=2;i<=T;i++){
            int p=i/2-1;
            int revP=T-p-1;
            if(i%2==1){
                  m=(m*10)%MOD;
                  mR=(mR*10)%MOD;
                  permDP[0][0]=1;
                  for(int j=0;j<10;j++){
                        for(int k=0;k+j<LIMIT;k++){
                              dp[p+1][k+j]=    (dp[p+1][k+j]    +dp[p][k]      +j*mR*permDP[p][k])%MOD;
                              dp[revP-1][k+j]= (dp[revP-1][k+j] +dp[revP][k]*10+j*permDP[revP][k])%MOD;
                              permDP[p+1][k+j]=(permDP[p+1][k+j]+permDP[p][k])%MOD;
                              permDP[revP-1][k+j]=(permDP[revP-1][k+j]+permDP[revP][k])%MOD;
                        }    
                  }
            }
            __int64 d=ans;
            __int64 test;
            for(int j=0;j<LIMIT;j++){
                  //if(permDP[p][j]==0||permDP[revP][j]==0)continue;
                  test=((i%2==0?0:permDP[p][j]*permDP[revP][j])%MOD*mR*45)%MOD;
                  temp=((dp[p][j]*permDP[revP][j])%MOD*(i%2==1?10:1)+(dp[revP][j]*m)%MOD*permDP[p][j]*(i%2==1?10:1)+test)%MOD;
                  ans=(ans+temp)%MOD;
            }
            std::cout<<"T="<<i<<" "<<ans<<" d"<<ans-d<<"\n";
      }
      std::cout<<"ans="<<ans<<"\n";
}