AHOI2012树屋阶梯

这玩意不是卡特兰的经典模型吗……

我们设方案数为f(i)，则f(0)=1,f(1)=1，f(2)=2,f(3)=5，（其实到这里你再手模一个就出来了）我们把左上角的矩形删掉，则会变成下方和右方两个更小规模的问题（如果没有就是f(0)喽），拿样例举例f(3)=f(2)的一种情况*f(0)+f(2)的另一种情况*f(0)+f(1)*f(1)+f(0)*f(2)的一种情况+f(0)*f(2)的另一种情况，总结一下，f(3)=$∑_{i=0}^{2}f(i)*f(2-i)$，对所有情况进行归纳，则得到Cat数O(n^2)的那个递归的式子。

至于算的时候，直接O(n)唯一分解接高精就搞定了，（至于你不懂什么叫O(n)唯一分解，你可以去看代码或上一篇博客）。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

int n,prime[],prime_num;

bool v[];

struct Bigint{

    int a[],len;

    void clear(){

        memset(a,,sizeof(a));

        len=;

        a[]=;

    }

    friend void operator *(Bigint &x,int y){

        int delta=;

        for(int i=;i<=x.len;i++){

            x.a[i]=x.a[i]*y+delta;

            delta=x.a[i]/;

            x.a[i]%=;

        }

        while(delta>){

            x.a[++x.len]=delta%;

            delta/=;

        }

        while(x.a[x.len]==&&x.len>)

            --x.len;

    }

    void out(){

        for(int i=len;i>=;i--)

            printf("%d",a[i]);

    }

}ans;

void doprime(int x){

    for(int i=;i<=x;i++){

        if(!v[i]) prime[++prime_num]=i;

        for(int j=;j<=prime_num&&i*prime[j]<=x;j++){

            v[i*prime[j]]=;

            if(i%prime[j]==) break;

        }

    }

}

int main(){

    scanf("%d",&n);

    doprime(*n+);ans.clear();

    for(int i=;i<=prime_num;i++){

        long long s=;

        for(int j=*n;j/=prime[i];) s+=j;

        for(int j=n;j/=prime[i];) s-=j;

        for(int j=n+;j/=prime[i];) s-=j;

        for(int j=;j<=s;j++)

            ans*prime[i];

    }

    ans.out();

    return ;

}

至此Cat三题吸收完毕。

巴特西

AHOI2012树屋阶梯

最新文章

热门文章