P13862 [SWERC 2020] Mentors

· · 题解

这么水的蓝没人做？

::::info[题意]{open} 有 n 个人，当 a>b 时，a 可以是 b 的老师，只有 n 没有老师，其他人有且仅有 1 个老师，且每个老师有 0 到 2 个学生，r 不能是别人的老师，求方案数对 m 取模。 ::::

::::info[题解]{open} 题目给出可以顺序处理，也就是每个人在之前的点中选学生的问题，且之前没有老师的学生可以被后面的人选择。考虑 DP。

设 f_{i,j} 为前 i 个人中有 j 个人还没有老师。

那么对于 i=r：

f_{i,j} \leftarrow f_{i-1,j-1}

对于 i \neq r：

f_{i,j} \leftarrow f_{i-1,j-1} + f_{i-1,j} \cdot j + f_{i-1,j+1} \cdot \frac{j(j+1)}{2}

三项分别为：

  1. 等待后面人选他，没有老师的人增加一个；
  2. 在 1 基础上选一个学生，有 j 种选择；
  3. 在 1 基础上选两个学生，有 \frac{j(j+1)}{2} 种选择。

答案为 f_{n,1}，因为 n 没有老师。 ::::

::::success[参考程序] 超短。

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

const int N = 2026;

int n, m, r, dp[N][N];

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> r >> n >> m;
    dp[1][1] = 1;
    for(int i = 2; i <= n; ++ i){
        if(i == r){
            for(int j = 1; j <= i; ++ j)
                dp[i][j] = dp[i - 1][j - 1];
        }
        else{
            for(int j = 1; j <= i; ++ j)
                dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 1][j] * j % m) % m + dp[i - 1][j + 1] * ((j * (j + 1) / 2) % m) % m) % m;
        }
    }
    cout << dp[n][1];

    return 0;
}

::::