제출 #22603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22603		거북선 (#40)	Fully Generate (KRIII5_FG)	C++98	0 / 7	0 ms	41080 KiB

FG

#include<iostream>
#include<vector>

using namespace std;

int n;
int arr[10000000] = { 0 };
pair<int, int> c;
long long mod = 1000000007;
long long ans=1;

long long cal(int num, int a)
{
	if (a == 1) return num;
	else if (a == 2) 
		return num*num%mod;
	int temp = cal(num, a / 2) % mod;
	
	if ((a % 2) == 0) return temp*temp%mod;
	return cal(num,a-1)*num%mod;
}
void go(int num, int sum)
{
	if(arr[num]==0)
		arr[num] = c.first;
	int tsum = sum + arr[num];
	if (tsum >= n)
	{
		ans*=cal(num, n - sum);
		ans %= mod;
		return;
	}
	//pop
	c.second--;
	ans *= cal(num, c.first);
	ans %= mod;
	arr[num] = c.first;
	//push
	if (c.second == 0)
	{
		c.first++;
		c.second = arr[c.first];
	}
	go(num + 1, tsum);
}

int main()
{
	cin >> n;
	arr[1] = 1;
	arr[2] = 2;
	c.first = 1;
	c.second = 1;
	go(1, 0);
	cout << ans;

	return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5