Codeforces Global Round 14 E. Phoenix and Computers

题目链接

点我跳转

题目大意

解题思路

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 4e2 + 10;
long long C[N][N] , bit[N];
long long n , m , ans , f[N][N];
void init(int mod)
{
	bit[0] = 1;
	for(int i = 1 ; i <= N - 10 ; i ++) bit[i] = bit[i - 1] * 2 % mod;
	for(int i = 0 ; i <= N - 10 ; i ++)
	{
		C[i][0] = 1;
		for(int j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
}
signed main()
{
	cin >> n >> m;
	init(m);
	for(int i = 1 ; i <= n ; i ++)
	{
		f[i][i] = bit[i - 1];
		for(int j = 0 ; j <= i ; j ++)
		{
			for(int k = 1 ; k + i + 1 <= n; k ++)
			{
				f[i + 1 + k][j + k] += f[i][j] * bit[k - 1] % m * C[j + k][k] % m;
				f[i + 1 + k][j + k] %= m;
			}
		}
	}
	for(int i = 0 ; i <= n ; i ++) ans += f[n][i] , ans %= m;
	cout << ans << '\n';
	return 0;
}