题目分析

题目要求计算在满足严格递减条件的矩阵排列中，cz_?? 相邻妹子数量的期望。核心在于统计所有合法排列中 cz_?? 相邻妹子的总数，再除以合法排列的总数。由于矩阵规模较小（(n+m \leq 20)），可通过状态压缩动态规划（DP）结合组合计数求解。

解题思路

1. 状态表示：用二进制状态表示矩阵每列的填充高度，通过DFS预处理所有合法状态。
2. DP预处理：
   • 正向DP：从最高身高开始填充，统计每个状态下的排列数及相邻妹子的贡献。
   • 反向DP：从cz_??的位置反向填充，统计后续排列的贡献。
3. 组合计数：结合正向和反向DP结果，计算cz_??相邻妹子的总贡献，最终除以总排列数得到期望。

代码实现（带注释）

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef bool boolean;

const int N = 20, S = 2e5, M = 105, Mod = 1e9 + 7;
const int None = N << 1;  // 表示无相邻贡献的状态

// 扩展欧几里得算法求逆元
void exgcd(int a, int b, int &x, int &y) {
    if (!b)
        x = 1, y = 0;
    else {
        exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
}

// 求a在模n下的逆元
int inv(int a, int n) {
    int x, y;
    exgcd(a, n, x, y);
    return (x < 0) ? (x + n) : (x);
}

// 状态结构体：存储二进制状态、块数、ID
typedef class Status {
public:
    int s, block, id;
    Status() {  }
    Status(int s, int block, int id): s(s), block(block), id(id) {   }
    // 按块数排序
    boolean operator < (Status b) const {
        return block < b.block;
    }
} Status;

int n, m, student;
pair<double, char> hei[M];  // 存储身高和性别
char ord[M];                // 排序后的性别序列
int id[1 << N];             // 状态到ID的映射
int f[S][N << 1 | 1];       // 正向DP：f[状态][位置] = 排列数/贡献
int g[S][N << 1 | 1];       // 反向DP：g[状态][位置] = 排列数/贡献
int cnts = 0;               // 状态总数
Status sord[S];             // 排序后的状态
int ar[N], br[N];           // 辅助数组，存储每列高度

// 将列高度数组编码为二进制状态
int coding(int *ar) {
    int rt = 0, lim = m;
    for (int i = 0; i < n; i++) {
        while (lim > ar[i])
            lim--, rt <<= 1;
        rt = rt << 1 | 1;
    }
    return rt << lim;
}

// 将二进制状态解码为列高度数组
void decode(int *ar, int s) {
    int lim = 0, i = n;
    while (i) {
        while (!(s & 1))
            s >>= 1, lim++;
        ar[--i] = lim;
        s >>= 1;
    }
}

int rk = 0;  // cz_??在排序后的位置
char buf[10];

// 初始化：读取输入并排序身高
inline void init() {
    double hcz;
    scanf("%d%d%lf", &n, &m, &hcz);
    student = n * m;

    // 读取其他学生信息
    for (int i = 0; i < student - 1; i++) {
        scanf("%lf%s", &hei[i].first, buf);
        hei[i].second = buf[0];
    }
    // 添加cz_??的信息
    hei[student - 1] = make_pair(hcz, '.');

    // 按身高降序排序
    sort(hei, hei + student, greater< pair<double, char>>());

    // 记录排序后的性别序列，并找到cz_??的位置
    for (int i = 0; i < student; i++) {
        ord[i] = hei[i].second;
        if (ord[i] == '.')
            rk = i;
    }
}

// DFS预处理所有合法状态
void dfs(int dep, int last, int sta, int block) {
    if (dep == n) {  // 所有行处理完毕
        sta <<= last;  // 补全剩余位
        id[sta] = cnts;
        sord[cnts] = Status(sta, block, cnts);
        cnts++;
        return;
    }
    // 枚举当前行的高度
    for (int i = 0; i <= last; i++)
        dfs(dep + 1, i, sta << (last - i + 1) | 1, block + i);
}

// 模加法
int add(int a, int b) {
    a += b;
    if (a >= Mod)
        a -= Mod;
    return a;
}

// 位置编码：将(x,y)映射为唯一整数
#define pid(_x, _y) (n - (_x) + (_y))

// 检查位置(x,y)与j行的兼容性（正向DP）
boolean check1(int *ar, int x, int y, int j) {
    if (x == n - 1)
        return true;
    if (x == j)
        return ar[x + 1] < y;
    if (x + 1 == j)
        return ar[x] == y || (ar[x + 1] + 1 < y);
    return true;
}

// 检查位置(x,y)与j行的兼容性（反向DP）
boolean check2(int *ar, int x, int y, int j) {
    if (!x)
        return true;
    if (x == j)
        return ar[x - 1] > y;
    if (x - 1 == j)
        return ar[x] == y || (ar[x - 1] - 1 > y);
    return true;
}

int tr[N];  // 临时存储状态转移

// 主求解函数
inline void solve() {
    // 预处理所有合法状态
    dfs(0, m, 0, 0);
    sort(sord, sord + cnts);  // 按块数排序

    // 初始化正向DP：初始状态（空矩阵）的排列数为1
    f[sord[0].id][None] = 1;

    // 正向DP：从最高身高开始填充
    for (int sti = 0; sti < cnts - 1; sti++) {
        int r = sord[sti].block;       // 当前填充的人数
        int si = sord[sti].id;         // 当前状态ID
        decode(ar, sord[sti].s);       // 解码列高度
        memcpy(br, ar, sizeof(ar));    // 复制状态
        memset(tr, -1, sizeof(tr));    // 初始化转移数组

        // 尝试填充每个位置
        for (int i = 0, s; i < n; i++)
            if (ar[i] < m && (!i || ar[i - 1] > ar[i])) {  // 合法填充位置
                br[i]++;  // 填充当前列
                tr[i] = s = id[coding(br)];  // 新状态ID
                // 更新排列数
                f[s][None] = add(f[s][None], f[si][None]);
                // 如果当前是妹子，记录贡献
                if (ord[r] == 'G')
                    f[s][pid(i, br[i])] = add(f[s][pid(i, br[i])], f[si][None]);
                br[i]--;  // 恢复状态
            }

        // 处理相邻贡献的转移
        for (int x = 0; x < n; x++) {
            for (int y = ((x < n - 1) ? (ar[x + 1] + (ar[x + 1] != ar[x])) : (0)); y <= ar[x]; y++)
                if (ar[x] && y && f[si][pid(x, y)])
                    for (int j = 0, s; j < n; j++)
                        if ((s = tr[j]) != -1 && check1(ar, x, y, j))
                            f[s][pid(x, y)] = add(f[s][pid(x, y)], f[si][pid(x, y)]);
        }
    }

    // 反向DP：从cz_??的位置反向填充
    int ends = sord[cnts - 1].id;  // 填满矩阵的状态ID
    g[ends][None] = 1;             // 初始化反向DP

    for (int sti = cnts - 1; sti; sti--) {
        int r = sord[sti].block - 1;  // 当前填充的人数（反向）
        int si = sord[sti].id;        // 当前状态ID
        if (r == rk) break;           // 到达cz_??的位置，停止

        decode(ar, sord[sti].s);     // 解码列高度
        memcpy(br, ar, sizeof(ar));  // 复制状态
        memset(tr, -1, sizeof(tr));  // 初始化转移数组

        // 尝试反向填充每个位置
        for (int i = 0, s; i < n; i++)
            if (ar[i] && (i == n - 1 || ar[i] > ar[i + 1])) {  // 合法反向填充位置
                br[i]--;  // 反向填充
                tr[i] = s = id[coding(br)];  // 新状态ID
                // 更新排列数
                g[s][None] = add(g[s][None], g[si][None]);
                // 如果当前是妹子，记录贡献
                if (ord[r] == 'G')
                    g[s][pid(i, br[i])] = add(g[s][pid(i, br[i])], g[si][None]);
                br[i]++;  // 恢复状态
            }

        // 处理相邻贡献的转移
        for (int x = 0; x < n; x++)
            for (int y = ((x) ? (ar[x - 1] - (ar[x - 1] != ar[x])) : (m)); y >= ar[x]; y--)
                if (ar[x] < m && y < m && g[si][pid(x, y)])
                    for (int j = 0, s; j < n; j++)
                        if ((s = tr[j]) != -1 && check2(ar, x, y, j))
                            g[s][pid(x, y)] = add(g[s][pid(x, y)], g[si][pid(x, y)]);
    }

    // 计算总贡献
    int res = 0;
    for (int sti = 0; sti < cnts; sti++) {
        int r = sord[sti].block;  // 当前填充人数
        if (r == rk + 1) {        // 处理cz_??的下一个状态
            decode(ar, sord[sti].s);
            memcpy(br, ar, sizeof(ar));

            // 枚举cz_??的相邻位置
            for (int i = 0, s; i < n; i++)
                if (ar[i] && (i == n - 1 || ar[i] > ar[i + 1])) {
                    br[i]--;
                    s = id[coding(br)];

                    // 统计上方、右侧、左侧、下方的妹子贡献
                    if (br[i])
                        res = add(res, f[s][pid(i, br[i])] * 1ll * g[sord[sti].id][None] % Mod);
                    if (ar[i] < m)
                        res = add(res, f[s][None] * 1ll * g[sord[sti].id][pid(i, ar[i])] % Mod);
                    if (i)
                        res = add(res, f[s][pid(i - 1, ar[i])] * 1ll * g[sord[sti].id][None] % Mod);
                    if (i < n)
                        res = add(res, f[s][None] * 1ll * g[sord[sti].id][pid(i + 1, br[i])] % Mod);

                    br[i]++;
                }
        }
    }

    // 计算期望：总贡献 / 总排列数
    res = res * 1ll * inv(f[ends][None], Mod) % Mod;
    printf("%d\n", res);
}

int main() {
    init();   // 初始化输入
    solve();  // 求解
    return 0;
}

代码解释

1. 状态预处理：通过DFS生成所有合法的矩阵填充状态，并编码为二进制。
2. 正向DP：从最高身高开始填充，统计每个状态下的排列数及妹子贡献。
3. 反向DP：从填满矩阵的状态反向推导，统计cz_??位置后的贡献。
4. 结果计算：结合正反向DP结果，计算cz_??相邻妹子的总贡献，除以总排列数得到期望，并通过逆元处理模运算。