プロジェクトオイラー 失敗作 問258

プロジェクトオイラー問258を解くコードを書こうとして失敗しました。


解法
数字列を2000個ごとで一行として、その行から次の行を求める漸化式を考えます。
漸化式を立てると一行先を求める漸化式の係数から2行先を求める漸化式の係数が。
2行先を求める漸化式の係数から4行先がと求まります。
以後同じ処理を繰り返すことで2倍2倍で増える先の行を求める漸化式が手に入ります。
がこれは10＾18をそのまま愚直に求めるのより単純計算200万倍速いだけで、ループ処理が入るのでさらに遅くなり、コードを実行したところ正しい答えが出るまで23時間もかかりました。
私の使ってるパソコンかＢＣＣ5.5どちらが悪いのかわかりませんがコンパイル結果のＭｏｄ演算が妙に遅いということを加味してもこれは恥ずべき結果です。




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


const int LIMITER=2000;
const __int64 MOD=20092010;

struct Vec{
__int64 es[LIMITER];
void add_and_mult(Vec& v,int t){
for(int i=0;i<LIMITER;i++){
es[i]=(es[i]+v.es[i]*t)%MOD;
}
}
void reset(){
memset(es,0,sizeof(es));
}
};

int main(){
std::vector<Vec> dp[2];
Vec v1,v2,v3;
__int64 row=pow(10,18);
row=row/LIMITER;
std::cout<<row<<"\n";
v1.reset();
for(int i=0;i<LIMITER;i++){
dp[1].push_back(v1);
}

for(int i=0;i+1<LIMITER;i++){
v1.reset();
v1.es[i]=v1.es[i+1]=1;
dp[0].push_back(v1);
}
v1.reset();
v1.es[0]=v1.es[1]=v1.es[LIMITER-1]=1;
dp[0].push_back(v1);

__int64 rowData[2][LIMITER];
for(int i=0;i<LIMITER;i++)rowData[0][i]=1;
__int64 add,ans=1;
int turn=0;
int point=0;
while(row>0){
std::cout<<"\n row="<<row<<" ";
if(row%2==1){
int now=point;
int next=(point+1)%2;
int now1=turn%2;
memset(rowData[next],0,sizeof(rowData[next]));
for(int i=0;i<LIMITER;i++){
for(int j=0;j<LIMITER;j++){
add=(rowData[now][j]*dp[now1][i].es[j])%MOD;
rowData[next][i]=(rowData[next][i]+add)%MOD;
}
}
std::cout<<" ans="<<rowData[next][0];
point=(point+1)%2;
ans=rowData[next][0];
}
int now=turn%2;
int next=(turn+1)%2;
for(int i=0;i<LIMITER;i++){
dp[next][i].reset();
for(int j=0;j<LIMITER;j++){
if(dp[now][i].es[j]==0)continue;
dp[next][i].add_and_mult(dp[now][j],dp[now][i].es[j]);
}
}
turn++;
row/=2;
}
std::cout<<"\n lastAns="<<ans;
}