P4921 [MtOI2018] 情侣？给我烧了！ 题解（评分：7.3）

· · 题解

前言

普通的计数题，我们普通地 dp。

这是一个不带脑子的 dp 做法。

Solution

观察数据范围：T\le1000,n\le 1000

本题只有一个 T=1000 的数据点。。。暴力还是算了吧！

这不就是让我们把 n=1 到 n=1000 所有答案计算一遍嘛！

这启示我们直接 dp！

设 dp_{i,j} 表示 i 对小情侣，有 j 对坐一起的方案数。

现在考虑加上一对新的推出 i+1。

先钦定两个人，男的先选（不考虑南通）

  1. 这对新的有可能坐一起，此时有 2\times (i+1) 种情况（男的随便选，妹子只能坐他旁边）

    此时其他的必然不打乱，所以总共坐一起的小情侣增加一对。

    对应：

    dp_{i+1,j+1}→dp_{i+1,j+1}+2\times (i+1)\times dp_{i,j}

  2. 这对新的没有坐一起，共有 (2\times i+2)\times 2\times i 种情况（妹子除了不坐他旁边还有 2\times i 个位置可以选择）。这样还可能打乱前面的，我们钦定这种情况时候，前面 2\times (i-1) 个人的位置不变，最后两人依次和这新来的两个人坐。

    显然坐一起的小情侣不会增加，而且会减少一对，当且仅当本来坐最后一排两个位置的是小情侣。

    但是在本来的 dp_{i,j} 种情况中，容易发现只有 \frac{j}{i} 的情况下坐最后一排两人是一对。

    那我们分开转移即可，具体的：

    dp_{i+1,j-1}→dp_{i+1,j-1}+dp_{i,j}\times (2\times i+2)\times 2\times i\times \frac{j}{i} dp_{i+1,j}→dp_{i+1,j}+dp_{i,j}\times (2\times i+2)\times 2\times i\times \frac{i-j}{i}

式子里有除法，但是可以约掉而不用写逆元。

搞定。

这里祝天下 xql 一律 99。（）

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int dp[1005][1005],i,j;
signed main()
{
    dp[1][1]=2;
    for(i=1;i<=999;i++)
    for(j=0;j<=i;j++) if(dp[i][j])
    {
        dp[i+1][j+1]=(dp[i+1][j+1]+2ll*(i+1)*dp[i][j])%mod;
        int dw=dp[i][j]*(i*4+4)%mod,br=dw*j,nb=dw*(i-j);
        if(j) dp[i+1][j-1]=(dp[i+1][j-1]+br)%mod;
        (dp[i+1][j]+=nb)%=mod;
    }
    int T;cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(i=0;i<=n;i++) cout<<dp[n][i]<<endl;
    }
    return 0;
 }

The End.