比赛 2024暑期C班集训4 评测结果 WWWTTTTTTT
题目名称 玩具 最终得分 0
用户昵称 djyqjy 运行时间 7.050 s
代码语言 C++ 内存使用 5.16 MiB
提交时间 2024-07-04 11:40:30
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n;
long long p;
long long sum[N];
long long qwzi=0,qwmu=1;
long long gcd(long long a,long long b)
{
    if(!b) return a;
    return gcd(b,a%b);
}
void dfs(int c,long long zi,long long mu)
{
    if(c>n)
    {
        long long maxx=0;
        for(int i=1;i<n;i++)
            maxx=max(maxx,sum[i]);
        long long zii=zi*maxx,muu=mu;
        long long g=gcd(zii,muu);
        zii/=g;
        muu/=g;
        long long qwmuu=qwmu*muu,qwzii=(qwzi*muu)%p+(zii*qwmu)%p;
        g=gcd(qwmuu,qwzii);
        qwmu=qwmuu;
        qwzi=qwzii;
        return;
    }
    for(int i=1;i<c;i++)
    {
        sum[i]++;
        long long zii=zi,muu=mu;
        muu*=c-1;
        long long g=gcd(zii,muu);
        zii/=g;
        muu/=g;
        dfs(c+1,zii,muu);
        sum[i]--;
    }
    return;
}
long long qpow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    freopen("toyy.in","r",stdin);
    freopen("toyy.out","w",stdout);
    scanf("%d%lld",&n,&p);
    if(n<=2)
    {
        if(n==1) printf("0");
        else if(n==2) printf("1");
        return 0;
    }
    sum[1]=1;
    dfs(3,1,1);
    printf("%lld",(qwzi*qpow(qwmu,p-2))%p);
    return 0;
}