제출 #20021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20021		noslaak	괄호 (kriii4_R)	C++98	0 / 100	2000 ms	2500 KiB

R

#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 / 8
• Subtask 2: 0 / 92