题解 AT3962 [ Sequence Growing Hard ]

CHHC · 2020-10-17 20:51:30 · 题解

题意

给定N,K,M，求满足以下条件的(N+1)元序列组(A_0,A_1,…,A_N)的数量，mod M。

对于任意i，序列A_i由1~K之间的整数构成，长度为i。
对于任意i>1，序列A_{i-1}是序列A_i的子序列。
对于任意i>1，序列A_{i-1}在字典序意义下严格小于序列A_i。
思路

考虑每次向第i个序列 “插入”元素时的情况。

因为要满足条件3，所以新插入的元素需要比上一个序列的插入位置的元素要大。可以发现，直接从小往大放是可以覆盖所有情况的。那么考虑去重，钦定当序列中有相同元素时在后面插入即可。

那么自然（……）有了dp状态：DP(i,j,k)表示考虑到第i个序列，放到数字j，在第k个数后面可以插入新的数字。

考虑转移：

当前状态下加入数字：DP(i+1,j,k)+=DP(i,j,k)*(k+1)。（注意可以放在末端，所以是k+1）
当前状态不加数字：DP(i,j,k-1)+=DP(i,j,k)。
考虑下一个数字：DP(i,j+1,k)+=DP(i,j,k)。

又是一道题面简单代码简单但是思维难度比较大的Atcoder（。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf = 1000000007ll;
int mod;

inline void add(int &x, int y)
{
    x += y;
    if (x > mod)
        x -= mod;
}

int N, M;
int dp[333][333][333];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> N >> M >> mod;
    dp[0][1][0] = 1;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            for (int k = i; k >= 0; k--)
            {
                int &cur = dp[i][j][k];
                if (!cur)
                    continue;
                if (!k)
                    add(dp[i][j + 1][i], cur); // 转移3
                else
                    add(dp[i][j][k - 1], cur); // 转移2
                if (i + 1 <= N)
                    add(dp[i + 1][j][k], cur * (k + 1) % mod); // 转移1
            }
        }
    }
    cout << dp[N][M][0] << endl;
    return 0;
}

题解 AT3962 [ Sequence Growing Hard ]

题意

思路

Code