제출 #22642

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

FG

#include<iostream>
#include<math.h>
#include<vector>

using namespace std;

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

void cal2(int num, int a)
{
	long long temp = pow(num, a / 2);
	if ((a % 2) == 0)
	{
		ans = ans*temp%mod;
		ans = ans*temp%mod;
	}
	else
	{
		ans = ans*num%mod;
		cal2(num, a - 1);
	}
}
void go(int num, int sum)
{
	if (arr[num] == 0)
		arr[num] = c.first;
	int tsum = sum + arr[num];
	if (tsum >= n)
	{
		cal2(num, n - sum);
		ans %= mod;
		return;
	}
	//pop
	c.second--;
	cal2(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