oj.uz

Submission #20021

# Submission time Handle Problem Language Result Execution time Memory
20021 2016-02-25T08:40:23 Z noslaak 괄호 (kriii4_R) C++
0 / 100
 2000 ms 2500 KB 
#include <iostream>

const int LN = 1000000007;
int modpow( long long A, long long X )
{
	int acc = 1;
	while(X)
	{
		A %= LN;
		if(X%2)
			acc = (A*acc)%LN;
		A = A*A;
		X /= 2;
	}
	return acc;
}

const int size = 100002;
int kinds[size][2];

int main()
{
	int N, K;
	while( std::cin >> N >> K )
	{
		int acc = 0;
		for( int i = 1; i <= N; ++i )
		{
			int prev = i%2 ? 0 : 1;
			int curr = i%2 ? 1 : 0;
			for( int j = 0; j <= i; ++j )
			{
				if( j == 0 )
				{
					kinds[j][curr] = 1;
				}
				else
				{
					kinds[j][curr] = kinds[j-1][curr] + kinds[j][prev];
				}

				if( i+j == N )
				{
					acc += modpow(K, i);
					acc %= LN;
				}
			}
			kinds[i+1][curr] = 0;
		}

		std::cout << acc << std::endl;
	}

	return 0;
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2500 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 92.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -