HDU4043_FXTZ II

时间:2025-02-12 14:33:33

题目描述的意思就不说了,自己考虑的时候就是在所有的排列中,碰到大于前面最大的出现数字的时候就乘以一个二分之一,然后求和。

打表后就会发现,答案分子为1*3*5*……*(2*n-1);分母为2*4*6*……*(2*n),这样就很简单了。

直接保存每一个因子出现的次数,然后。。。就可以了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#define M 1000000
#define maxn 1011
using namespace std; struct node{
int top,s[];
void init()
{
for (int i=; i<=top; i++) s[i]=;
top=,s[]=;
}
void mul(int x)
{
for (int i=; i<=top; i++) s[i]*=x;
for (int i=; i<top; i++)
if (s[i]>=M) s[i+]+=s[i]/M,s[i]%=M;
while (s[top]>=M) s[top+]=s[top]/M,s[top]%=M,top++;
}
void output()
{
printf("%d",s[top]);
for (int i=top-; i>=; i--) printf("%06d",s[i]);
}
}ans1,ans2; int a[maxn],pri[maxn],Pnum=;
bool b[maxn]; void getprim()
{
for (int i=; i<maxn; i++)
{
if (b[i]) continue;
pri[++Pnum]=i;
for (int j=i+i; j<maxn; j+=i) b[j]=true;
}
} void add(int x,int v)
{
for (int i=; pri[i]<=x; i++)
{
while (x%pri[i]==) x/=pri[i],a[i]+=v;
}
} int main()
{
int T,n;
getprim();
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
memset(a,,sizeof a);
for (int i=; i<=*n; i+=) add(i,);
for (int i=; i<=*n; i+=) add(i,-);
ans1.init(),ans2.init();
for (int i=; i<=Pnum; i++)
{
while (a[i]>) ans1.mul(pri[i]),a[i]--;
while (a[i]<) ans2.mul(pri[i]),a[i]++;
}
ans1.output();
printf("/");
ans2.output();
printf("\n");
}
return ;
}