HS
AFO
HS的博客
AT3962 Sequence Growing Hard

题目链接

AtCoder Grand Contest 024 E
AtCoder

题目描述

Find the number of the possible tuples of sequences $(A_0,A_1,…,A_N)$ that satisfy all of the following conditions, modulo $M$:

  • For every $i$ $(0\leq i\leq N)$, $A_i$ is a sequence of length $i$ consisting of integers between $1$ and $K$ (inclusive);
  • For every $i$ $(1\leq i\leq N)$, $A_{i-1}$ is a subsequence of $A_i$, that is, there exists $1\leq x_i\leq i$ such that the removal of the $x_i$-th element of $A_i$ would result in a sequence equal to $A_{i-1}$;
  • For every $i$ $(1\leq i\leq N)$, $A_i$ is lexicographically larger than $A_{i-1}$.

题目翻译

求满足下列条件的序列序列 $(A_0, A_1, …, A_N)$ 的个数:
– $A_i$是长度为 $i$,由 $[1, K]$ 组成的序列。
– $A_{i−1}$是 $A_i$ 的子序列。
– $A_i$字典序比 $A_{i−1}$大。

输入格式

Input is given from Standard Input in the following format:
N K M

输出格式

Print the number of the possible tuples of sequences $(A_0,A_1,…,A_N)$, modulo $M$.

输入输出样例

输入 #1

2 2 100

输出 #1

5

输入 #2

4 3 999999999

输出 #2

358

输入 #3

150 150 998244353

输出 #3

186248260

说明/提示

Five tuples below satisfy the conditions:

(),(1),(1,1)
(),(1),(1,2)
(),(1),(2,1)
(),(2),(2,1)
(),(2),(2,2)

$1 \leq N,K \leq 300$
$2 \leq M \leq 10^9$
$N$, $K$ and $M$ are integers.

分析

考虑序列序列的构造方式就是每次在前一个序列中插入一个数字$i$。
为了方便,我们认为插入的数字$i$之后的数字一定与$i$不同,如果相同,我们就往后插,这样构造出的序列是一样的。
为了满足字典序的限制,我们要让插入之后的数字小于插入的数字。
考虑如果这个数字是在第$i$次插入插入的,插入之后的数字是在第$j$次插入插入的,那么将$i \rightarrow j$连一条边,如果之后没有数字,我们连$i \rightarrow 0$。
这样我们就得到了一个树形结构。
这个树形结构每个点的权值是插入的数,设为$w$,标号是插入的时间。
那么题目就是要求这样的树形结构的个数,满足:

  • $fa < i$
  • $w_{fa} < w_i$

设$f_{i,j}$表示$i$个点的树形结构,根节点(标号为$0$)的权值为$j$。
转移就是:
$$
f_{i,j}=\sum_k\sum_{v>j}f_{i-k,j} \times f_{k,v} \times \binom{i-2}{k-1}
$$
就是枚举其中根节点标号为$1$子树的大小和根节点权值,因为标号是相对的,所以合并的时候要重新分配标号,由于根节点和枚举的子树标号确定了($0$和$1$),还剩$i-2$个标号,选出$k-1$个给枚举的子树,剩下的标号给剩下的子树,由于子树中标号大小是有相对顺序的,所以对于组合数计算的每个方案都只有唯一的放法。
最后前缀优化一下就是$O(n^2k)$了。

一些对我而言的坑

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 310
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,m,p,f[maxn][maxn],C[maxn][maxn];
int add(int x,int y)
{
    x+=y;
    return x>=p? x-p:x;
}
int mul(int x,int y)
{
    return 1ll*x*y%p;
}
int main()
{
    read(n,m,p);
    C[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    }
    for(int i=0;i<=m;i++)
        f[1][i]=1;
    for(int i=2;i<=n+1;i++)
    {
        for(int k=1;k<i;k++)
        {
            int t=0,c=C[i-2][k-1];
            for(int j=m;j>=0;j--)
            {
                f[i][j]=add(f[i][j],mul(mul(c,t),f[i-k][j]));
                t=add(t,f[k][j]);
            }
        }
    }
    printf("%d\n",f[n+1][0]);
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

AT3962 Sequence Growing Hard
模型转化,前缀优化DP
扫描二维码继续阅读
2020-01-11