#168744 (C++11) No.16 累乗の加算

• 問題: No.16 累乗の加算
• ユーザー: Klay
• 提出日時: 2017-04-26 22:47:15
• 言語: C++11 (gcc 11.4.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	MLE	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	MLE	-
testcase_07	MLE	-
testcase_08	MLE	-
testcase_09	MLE	-
testcase_10	MLE	-
testcase_11	MLE	-
testcase_12	MLE	-
testcase_13	MLE	-

ソースコード

#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;
}