比赛 |
2024暑期C班集训4 |
评测结果 |
AAATTTTTTT |
题目名称 |
玩具 |
最终得分 |
30 |
用户昵称 |
liuyiche |
运行时间 |
7.000 s |
代码语言 |
C++ |
内存使用 |
4.36 MiB |
提交时间 |
2024-07-04 09:34:41 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, p;
ll ans = 0, cnt = 0;
struct node
{
int dep;
};
vector<node> v(205);
inline void dfs(int step, int Max, ll c)
{
if(step == n+1)
{
ans += Max*c;
ans %= p;
cnt += c;
return;
}
unordered_map<int,ll> m;
for(int i = 1; i < step; ++i)
{
m[v[i].dep+1]++;
m[v[i].dep+1] %= p;
}
for(auto it : m)
{
v[step].dep = it.first;
dfs(step+1,max(Max,v[step].dep),c*it.second%p);
}
}
inline ll qpow(ll x, ll y)
{
if(y == 0)
return 1;
ll tmp = qpow(x,y/2);
tmp %= p;
tmp *= tmp;
tmp %= p;
if(y%2 != 0)
tmp *= x, tmp %= p;
//cout << tmp << " ";
return tmp;
}
int main()
{
freopen("toyy.in", "r", stdin);
freopen("toyy.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> p;
v[1].dep = 0;
dfs(2,0,1);
//cout << qpow(cnt,p-2)%p;
cout << ans*qpow(cnt,p-2)%p;
return 0;
}
/*10 1000000007
29089510*/