プロジェクトオイラー Problem 250 「250250」 †

Problem 250 「250250」 †

要素の合計が 250 で割り切れるような, {11, 22, 33,..., 250250250250} の空でない部分集合の数を求めよ. 最下位の 16 桁を答えとして入力せよ.

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






解法
難易度の低いサービス問題のようです。
何も考えない動的計画法で片が付きます。
難易度低すぎで他の難問の中で浮いてますねこの問題。
プログラム　Ｃ++　ＢＣＣ5.5


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

const int MOD=250;

int mod_pow(int n){
      int r=n,baseM=n % MOD,result=1;
      while(r>0){
            if(r%2==1){
                  result=(result*baseM) % MOD;
            }
            r/=2;
            baseM=(baseM*baseM) % MOD;
      }
      return result;
}
int main(){
      __int64 dp[2][MOD];
      __int64 MOD_LIMIT=100000000;
      MOD_LIMIT*=100000000;
      memset(dp,0,sizeof(dp));
      int now,next;
      for(int i=1;i<=250250;i++){
            now=i%2;
            next=(i+1)%2;
            memcpy(dp[next],dp[now],sizeof(dp[next]));
            int add=mod_pow(i);
            dp[next][add]+=1;
            for(int i=0;i<MOD;i++){
                  dp[next][(i+add) % MOD]=(dp[next][(i+add)%MOD]+dp[now][i])%MOD_LIMIT;
            }
      }
      std::cout<<dp[next][0]<<"\n";
}