题解 P3757 【[CQOI2017]老C的键盘】

· · 题解

哇塞！我可以说这是双倍经验吗？

和P4099HEOI2014SAO是重题，而且弱化了!!!

我也是不想说啥了……明明有O(n^2)的复杂度啊……

我可以贴一发我的题解链接嘛……

https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4099

那么我们发现对比HEOI2014来讲，这道题唯一的问题是，没有树QAQ

但是如果你对二叉树的表示相当熟练的话，我们会发现，其实线段树什么的啊，二叉堆什么的啊，都是用2*i，2*i+1来表示父子关系的i/2就是i的父亲，所以树什么的是可以建出来的，还是一只完全二叉树，

如果我们把它的拓扑序排名作为全排列里的位置，那么一个拓扑序一一对应一个全排列

所以是给定二叉树型图，求所有合法拓扑序方案，还只要求O(N^3)算法！

还有就是这道题连小于大于号都给你了……，你甚至不必改HEOI那道题的代码

当然我就只写O(N^3)的代码咯~，毕竟前缀和啥的还得再维护，多麻烦，出题人不为难你就不写了啊，写O(N^2)的去交4099

但是还有一个至关重要的麻烦，转移方程里，要求4个1e9乘一起，显然爆longlong…… 所以分开乘，膜3遍即可

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
ll mod=1e9+7;const int N=110;
ll dp[N][N];ll c[N][N];
ll siz[N];int n;ll res;
char mde[N];
inline void dfs(int x)
{
    for(int v=2*x;v<=min(n,2*x+1);v++)
    {
        dfs(v);
        if(mde[v]=='>')//O(N^3)因为我懒得打前缀和
        {
            for(int k=siz[x]+siz[v];k>=1;k--)//枚举排名
            {
                ll sum=0;
                for(int i=1;i<=min(siz[x],(ll)k);i++)//保证合法性的区间
                {
                    for(int j=k-i+1;j<=siz[v];j++)//保证合法性
                    {
                        ll a=(dp[x][i]*dp[v][j])%mod;ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod;
                        a=(a*b)%mod;sum=(sum+a)%mod;//两个序列的可能取值情况*x前序列组合*x后序列组合
                    }
                }
                dp[x][k]=sum;
            }
        }
        else//同上,只是枚举区间变了,转移方程是一样的
        {
            for(int k=siz[x]+siz[v];k>=1;k--)
            {
                ll sum=0;
                for(int i=1;i<=min(siz[x],(ll)k);i++)
                {
                    for(int j=1;j<=min((ll)k-i,siz[v]);j++)
                    {
                        ll a=(dp[x][i]*dp[v][j])%mod;ll b=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod;
                        a=(a*b)%mod;sum=(sum+a)%mod;
                    }
                }
                dp[x][k]=sum;
            }
        }
        siz[x]+=siz[v];//别忘了siz
    }
}
int main()
{
    scanf("%d",&n);
    c[0][0]=1;//打表组合数备用
    for(int i=1;i<=n;i++)
    {
        c[0][i]=1;c[i][i]=1;
        for(int j=1;j<i;j++){c[j][i]=(c[j][i-1]+c[j-1][i-1])%mod;}
    }
    scanf("%s",mde+2);//注意从2开始
    for(int i=1;i<=n;i++){dp[i][1]=1;siz[i]=1;}//初始化
    dfs(1);
    for(int i=1;i<=n;i++){res=(res+dp[1][i])%mod;}
    printf("%lld",res);return 0;//拜拜程序~
}