제출 #24606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24606		bill_kondo	캥거루 (CEOI16_kangaroo)	C++14	6 / 100	0 ms	2052 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 2e3 + 10;
const ll mod = 1e9 + 7;

int n, cs, cf;

ll dp[2][1 << 8][8];

ll f (int dir, int mask, int cur)
{
	if (dp[dir][mask][cur] == -1)
	{
		if (!mask)
		{
			if (cur != cf)
				return dp[dir][mask][cur] = 0;

			return dp[dir][mask][cur] = 1;
		}

		dp[dir][mask][cur] = 0;

		if (dir)
		{
			for (int i = cur; i < n; ++i)
				if ((1 << i) & mask)
					dp[dir][mask][cur] = (dp[dir][mask][cur] + f (dir ^ 1, mask - (1 << i), i)) % mod;
		}
		else
		{
			for (int i = cur; i >= 0; --i)
				if ((1 << i) & mask)
					dp[dir][mask][cur] = (dp[dir][mask][cur] + f (dir ^ 1, mask - (1 << i), i)) % mod;
		}
	}

	return dp[dir][mask][cur];
}

void solve_small ()
{
	memset (dp, -1, sizeof (dp));

	int total = (1 << n) - 1;
	cout << (f (0, total - (1 << cs), cs) + f (1, total - (1 << cs), cs)) % mod << '\n';
}

int main ()
{
	cin >> n >> cs >> cf;

	--cs;
	--cf;

	if (n <= 8)
	{
		solve_small();
		return 0;
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49