[ZJOI2010]排列计数

题目描述

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

输入输出格式

输入格式：

输入文件的第一行包含两个整数 n和p，含义如上所述。

输出格式：

输出文件中仅包含一个整数，表示计算1,2,⋯, ��的排列中， Magic排列的个数模 p的值。

输入输出样例

输入样例#1：

20 23

输出样例#1：

说明

100%的数据中，1 ≤N ≤ 10^6, P≤ 10^9，p是一个质数。

画图发现树的形状是唯一的

且对于一个子树的根，一定小于所有子树节点

也就是说，对于一个根节点，只要考虑给左右子树划分的方案
可以列出dp方程:

f[i]=f[2*i]*f[2*i+1]*C(size[2*i],size[2*i+1]+size[2*i])

这题据说n会大于p，也就是说1～n会含有p

那么就不能线性求逆元

统计出i!中p出现的次数num[i]和不算p的倍数的阶乘fac[i]

算组合数时，如果num[y]-num[x]-num[y-x]不为0直接返回0

逆元直接把fac[]带入拓展欧几里德，因为在算fac时排除了p，所以可行

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long lol;

 lol f[],size[],p,num[],fac[],n;

 lol exgcd(lol a,lol b,lol &x,lol &y)

 {

   if (b==)

     {

       x=;y=;

       return a;

     }

   lol d=exgcd(b,a%b,x,y);

   lol t=x;x=y;y=t-(a/b)*y;

   return d;

 }

 lol reverse(lol a)

 {

   lol x,y;

   exgcd(a,p,x,y);

   return (x%p+p)%p;

 }

 lol C(int x,int y)

 {

   lol ap=num[y],bp=num[x],cp=num[y-x];

   if (ap-bp-cp) return ;

   lol s=(fac[y]*reverse(fac[x])%p)*reverse(fac[y-x])%p;

   return s;

 }

 void dfs_dp(int x)

 {

   f[x]=;

   size[x]=;

   if (*x<=n)

     dfs_dp(*x);

   if (*x+<=n)

     dfs_dp(*x+);

   if (*x<=n)

   if (*x+>n||size[*x+]==)

     {

       f[x]=f[*x];

       size[x]+=size[*x];

     }

   else

     {

       f[x]=((f[*x]*f[*x+]%p)*C(size[*x],size[*x]+size[*x+])%p)%p;

       size[x]+=size[*x]+size[*x+];

     }

 }

 int main()

 {int i;

   cin>>n>>p;

   fac[]=;

   for (i=;i<=n;i++)

     {

       int x=i;

       num[i]=num[i-];

        while (x%p==)

     {

       num[i]++;

       x/=p;

     }

        if (i%p==) fac[i]=fac[i-];

        else fac[i]=fac[i-]*i%p;

     }

   dfs_dp();

   cout<<f[];

 }

巴特西

[ZJOI2010]排列计数

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章