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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20250
Problem 250 「250250」 †
要素の合計が 250 で割り切れるような, {1^1, 2^2, 3^3,..., 250250^250250} の空でない部分集合の数を求めよ. 最下位の 16 桁を答えとして入力せよ.

とりあえず何も考えない漸化式で（定型文だなこれ）答えが出ました。
計算時間３０秒。
多分一番平凡な解答。

賢い解答ならもっと早いと思います。

#include<stdio.h>
#include<iostream>
const int MOD=250;
const __int64 M8=pow(10,8);
const __int64 MOD16=M8*M8;

 
int f(int n){
	int m=n%MOD;
	int r=n;
	int ans=1;
	while(r>0){
		if(r%2==1){
			ans=(ans*m)%MOD;
		}
 		m=(m*m)%MOD;
		r/=2;
	}
	return ans;
}

int main(){
	__int64 ans[MOD]={0};
	__int64 next[MOD]={0};
	for(int i=1;i<=250250;i++){
		int add=f(i);
		for(int j=0;j<MOD;j++){
			int p=(add+j)%MOD;
 			__int64 c=ans[j];
			next[p]=(next[p]+c)%MOD16;
		}
		next[add]=(next[add]+1)%MOD16;
		memcpy(ans,next,sizeof(next));
	}
	std::cout<<ans[0]<<"\n";
}