首页 > 其他 > 详细

AtCoder Grand Contest 024 Problem E(动态规划)

时间:2018-07-08 19:58:50      阅读:172      评论:0      收藏:0      [点我收藏+]

www.cnblogs.com/shaokele/


AtCoder Grand Contest 024 Problem E

  Time Limit: 2 Sec
  Memory Limit: 1024 MB

Description

  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≤i≤N)\), \(A_i\) is a sequence of length \(i\) consisting of integers between \(1\) and \(K\) (inclusive);
  ? For every \(i\) \((1≤i≤N)\), \(A_{i-1}\) is a subsequence of \(A_i\), that is, there exists \(1≤x_i≤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≤i≤N)\), \(A_i\) is lexicographically larger than \(A_{i-1}\).
  

Input

  ? \(1≤N,K≤300\)
  ? \(2≤M≤109\)
  ? \(N, K\) and \(M\) are integers.
  
  Input is given from Standard Input in the following format:
  \(N K M\)
  

Output

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

Sample Input 1

  2 2 100
 

Sample Output 1

  5
  
  Five tuples below satisfy the conditions:
  ? (),(1),(1,1)
  ? (),(1),(1,2)
  ? (),(1),(2,1)
  ? (),(2),(2,1)
  ? (),(2),(2,2)
  

Sample Input 2

  4 3 999999999
 

Sample Output 2

  358
  

Sample Input 3

  150 150 998244353
 

Sample Output 3

  186248260
  

题目地址:  AtCoder Grand Contest 024 Problem E

题目大意:

  考虑 \(N + 1\) 个数组 \({A_0, A_1, . . . , A_N }\)
  其中 \(A_i\) 的长度是 \(i\),$A_i $内的所有数字都在 \(1\)\(K\) 之间。
  \(A_{i?1}\)\(A_i\) 的?序列,即 \(A_i\) 删?个数字可以得到 \(A_{i?1}\)
  \(A_i\) 的字典序?于 \(A_{i?1}\)
  输? \(N, K, M\) 问序列个数模 \(M\)

题解:

  我们可以认为 \(A_i\)\(A_{i?1}\) 插??个数字 \(x\) 得到的。
  为了让字典序变?,插?的 \(x\) 必须严格?于插?位置右侧的数字。
  题目解法一
  序列可以转化为?个树。
  ?个节点有 2 个属性,时间和权值。
  ?个节点的?亲节点,是插?位置右侧的,如果插?在末尾,右侧为空,那么?亲节点是 (0, 0)。
  时间必须唯?,权值可以是 \(1\)\(K\) 之间任选。
  每个点的时间和权值必须严格?于?亲节点的时间和权值。
   \(f[i][x]\) 表???为 \(i\) 的?树,根节点权值为 \(x\) 的?案数。
  \[f[i][x]=\sum_{1≤j≤i?1}\sum_{x<y≤K} f[i ? j][x] ? f[j][y] ? C(i ? 2, j ? 1)\]
  $\sum_{x<y≤K}f[j][y] $ 可以?部分和优化存。
  类似树形 DP 做?下就?了。
  参考代码
  题目解法二
  上??个做法,?较容易理解,但是写起来稍微?烦。需要预处理组合数。
  原本是元素?个?个加?进序列,序列慢慢变长。
  现在我们考虑,从?到?加?所有的元素。显然有先加??的,再加??的情况。
  加?较?元素的时候,我们不仅可以再最后?个序列中加?,也可以在之前的序列中加?。
  \(f[i][v][p]\),当前长度为 \(i\),从?到?依次插?权值,已插?到 \(v\),考虑在第 \(p\) 个序列加?。
  核?思想是从?到?插?权值,但是这样可能漏掉?些情况(先插??权值,再插??权值。)
  \(p\) 就为了解决这个问题,允许我们修改从前的过程。
  转移:
  \(f[i][v][p ? 1]+ = f[i][v][p]\) 不加?,考虑在第 \(p ? 1\) 个序列加?,要求 \((p > 0)\)
  \(f[i][v + 1][i]+ = f[i][v][p]\) 换更?的值,如果已经尝试到第 \(0\) 个序列了,要求 \((p = 0)\)
  \(f[i + 1][v][p]+ = f[i][v][p] ? (p + 1)\) 插??个,注意即使加?,下?次依然是第 \(p\) 个序列,?不是 \(p + 1\)
  空间复杂度 \(O(KN^2)\),可以优化为 \(O(KN)\)
  


AC代码

#include <cstdio>
using namespace std;
int N,K,mo;
int dp[305][305];
int main(){
    scanf("%d%d%d",&N,&K,&mo);
    dp[0][0]=1;
    for(int i=0;i<=N;i++)
        for(int j=0;j<K;j++)
            for(int k=i;k>=0;k--){
                if(k)dp[j][k-1]=(dp[j][k-1]+dp[j][k])%mo;
                else dp[j+1][i]=(dp[j+1][i]+dp[j][k])%mo;
                dp[j][k]=1ll*dp[j][k]*(k+1)%mo;
            }
    printf("%d\n",dp[K][N]);
    return 0;
}

AtCoder Grand Contest 024 Problem E(动态规划)

原文:https://www.cnblogs.com/shaokele/p/9280924.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!