結果

問題 No.16 累乗の加算
コンテスト
ユーザー Klay
提出日時 2017-04-26 22:47:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 1,123 bytes
コンパイル時間 588 ms
コンパイル使用メモリ 67,792 KB
実行使用メモリ 784,416 KB
最終ジャッジ日時 2024-09-13 12:51:40
合計ジャッジ時間 10,756 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 3 MLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<unsigned long long> dp;	//dp[n] = x^(n) % Z

unsigned long long x, N;

const unsigned long long Z = 1000003;

int getRest(int a)	//x^aの余り。
{
	unsigned long long result = 1;
	
	if(dp[a] != -1)
	{
		return dp[a];
	}
	
	if(a == 0)
	{
		return 1;
	}
	
	for(int i = 1; i <= a; i ++)	//a=3:i=1,2,3
	{
		result = (result * x) % Z;
		
		dp[i] = result;
		
		if(a - i != 0 && dp[a - i] != -1)
		{	
			//std::cout << result << " " << dp[a - i] << " ";
		
			result = (result * dp[a - i]) % Z;
			
			//std::cout << "used " << a - i << " " << result << " " << dp[a - i] << std::endl;
 			
 			break;
		}
	}
	
	dp[a] = result;
	
	return result;
}

int main(void)
{
	std::cin >> x >> N;
	
	x = x % Z;
	
	std::vector<int> a(N);
	
	for(int i = 0; i < N; i ++)
	{
		std::cin >> a[i];
	}
	
	std::sort(a.begin(), a.end());
	
	dp.resize(a[N - 1] + 1);
	std::fill(dp.begin(), dp.end(), -1);
	dp[0] = 1;
	
	//mod 1000003
	
	unsigned int result = 0;
	
	for(int i = 0; i < N; i ++)
	{
		result += getRest(a[i]);
	}
	
	std::cout << result << std::endl;

	return 0;
}
0