oj.uz

답안 #22706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22706 2017-04-30T06:44:52 Z 응 내인생 터졌어~(#957, sosfd) Fully Generate (KRIII5_FG) C++11
0 / 7
 0 ms 626116 KB 
#include <stdio.h>

unsigned long long dp[40000000],dp2[40000000];


int ass[100] = {0,1,2,4,12,36,144,576,2304,11520,57600};

long long go(int i)
{
	if (dp[i] !=0) return dp[i];


	return dp[i] =  1 + go(i - go(go(i - 1)));
}


unsigned long long po(unsigned int a, unsigned int b)
{
	if (b == 0)
		return 1;
	else if (b == 1)
		return a;

	unsigned long long ret = po(a, b/2) % 1000000007;

	ret = ret*ret;
	ret %= 1000000007;

	if (b % 2)
		return (ret* a)%1000000007;
	else
		return ret;

}

int main()
{
	dp[1] = 1;
	
	unsigned long long sum = 0,n,ans =36;
	scanf("%llu", &n);
	

	dp2[1] = 1;
	dp2[2] = 5;
	
	unsigned long long k = 3;


	if (n <=10)
	{
		printf("%d", ass[n]);
		return 0;
	}

	for (int i = 3; i < 40000000; i++)
	{
		dp2[i] = dp2[i - 1] + i*go(i);

		unsigned long long tt = 1,temp = dp2[i-1];

		for (int j = k + 1; j<=k + dp[i]; j++)
		{
			tt *= j;
			tt %= 1000000007;
			temp += i;

			if (temp >= n) // ������ ���
			{
				tt /= j;
				temp -= i;
				ans *= po(tt, i);

				ans %= 1000000007;
				ans *= po(j, n - temp);
				ans %= 1000000007;

				printf("%d", ans);
				return 0;
			}
		}
		
		k += dp[i];
		ans *= po(tt, i);
		ans %= 1000000007;
	} 

	return 0;
}

Compilation message

FG.cpp: In function 'int main()':
FG.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = k + 1; j<=k + dp[i]; j++)
                        ^
FG.cpp:78:21: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long unsigned int' [-Wformat=]
     printf("%d", ans);
                     ^
FG.cpp:40:21: warning: unused variable 'sum' [-Wunused-variable]
  unsigned long long sum = 0,n,ans =36;
                     ^
FG.cpp:41:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%llu", &n);
                   ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 626116 KB Output is correct
2 Correct 0 ms 626116 KB Output is correct
3 Correct 0 ms 626116 KB Output is correct
4 Correct 0 ms 626116 KB Output is correct
5 Correct 0 ms 626116 KB Output is correct
6 Correct 0 ms 626116 KB Output is correct
7 Correct 0 ms 626116 KB Output is correct
8 Correct 0 ms 626116 KB Output is correct
9 Correct 0 ms 626116 KB Output is correct
10 Correct 0 ms 626116 KB Output is correct
11 Incorrect 0 ms 626116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 626116 KB Output is correct
2 Correct 0 ms 626116 KB Output is correct
3 Correct 0 ms 626116 KB Output is correct
4 Correct 0 ms 626116 KB Output is correct
5 Correct 0 ms 626116 KB Output is correct
6 Correct 0 ms 626116 KB Output is correct
7 Correct 0 ms 626116 KB Output is correct
8 Correct 0 ms 626116 KB Output is correct
9 Correct 0 ms 626116 KB Output is correct
10 Correct 0 ms 626116 KB Output is correct
11 Incorrect 0 ms 626116 KB Output isn't correct
12 Halted 0 ms 0 KB -