【AHOI2013复仇】ZJOI2010 Perm 排列计数

Posted on 2012-10-30 21:35 Mato_No1 阅读(1021) 评论(1)  编辑 收藏 引用 所属分类: ZJOI数论组合数学
原题地址
这是个超级大水题,我太沙茶了,想傻了N久……后来才反应过来……所以要写一下作为警示。

首先这个序列就是一个堆……
因此,问题也就是说N个结点,权值刚好取遍1~N的堆的总数……
设结果为F[N]。设N个结点的堆,左子树有l个结点,右子树有r个结点(显然有l+r+1=N),则有
F[N]=C(N-1, l) * F[l] * F[r]
这个理解起来很容易囧……因为根结点只能是1,左子树和右子树显然也都是堆,因此相当于在2~N中取l个数组成左子树,剩下的数组成右子树……又因为不管取哪些数,左右子树的组成方法总数都是F[l]、F[r](只与次序有关)……这样就得到上面的式子了囧……
C(N-1, l)=N! / l! / r!,因此需要预处理出来A[i] = i! mod P,然后除法用逆元就行了囧……

不过,本沙茶一开始想按照层数枚举,然后相乘……自然搞不出来囧……后来又用暴力把N<=15的结果拿出来分析,想找到规律……结果毫无规律……后来又纠结了N久才想到上面这个……真正比赛的时候就悲剧了囧……所以要警示一下……

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 1000010, INF = ~0U >> 2;
int n;
ll MOD, A[MAXN], F[MAXN], res;
void init()
{
    cin 
>> n >> MOD;
}
void prepare()
{
    A[
0= A[1= 1; re3(i, 2, n) A[i] = (A[i - 1* i) % MOD;
}
void exgcd(ll a, ll b, ll &x, ll &y)
{
    
if (b) {
        ll _x, _y; exgcd(b, a 
% b, _x, _y);
        x 
= _y; y = _x - (a / b) * _y;
    } 
else {x = 1; y = 0;}
}
void solve()
{
    F[
0= F[1= 1int s = 1, l = 0, r = 0; ll x, y;
    re3(i, 
2, n) {
        
if (l == s) {
            
if (r == s) {s += s + 1; l++;} else r++;
        } 
else l++;
        F[i] 
= F[l] * F[r] % MOD; F[i] = F[i] * A[i - 1% MOD;
        exgcd(A[l], MOD, x, y); F[i] 
= F[i] * x % MOD; if (F[i] < 0) F[i] += MOD;
        exgcd(A[r], MOD, x, y); F[i] 
= F[i] * x % MOD; if (F[i] < 0) F[i] += MOD;
    }
    res 
= F[n];
}
void pri()
{
    cout 
<< res << endl;
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}

Feedback

# re: 【AHOI2013复仇】ZJOI2010 Perm 排列计数  回复  更多评论   

2014-06-24 00:05 by tankche2
数据加强后您的程序好想在bzoj上被卡掉了

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理