比赛 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*/