比赛 |
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;
}