@noi.ac - [emailprotected] 数数

@[email?protected]

求有多少对 1 ～ n 的排列 (a,b) 满足 (m le sum_{i=1}^{n}max(ai,bi))。

两个方案 (a,b) 和 (a′,b′) 不同当且仅当存在 i 使得 (ainot =a′i)或 (binot =b'i)。

input
一行两个整数 n,m。

output
一行一个整数表示答案。对 998244353 取模。

sample input
3 8
sample output
18

对于100%的数据，1≤n≤50，1≤m≤10^9。

@[email?protected]

根据我多年 OI 经验，题目短的不是水就是毒瘤。
但是这一次我好像A了这道题。
看到998244353是不是感觉整个人都不好了。

可以发现 a 中元素与 b 中元素的一一对应的关系确定了 (sum_{i=1}^{n}max(ai,bi))。
所以我们可以只统计 a 与 b 中元素对应关系合法的方案，再乘上 n! 表示全排列。

另外还可以发现，题目所给的和式其中一个上界为 n*n（可以发现这是一个不是很紧的上界，但足够了）。故当 m > n*n 时直接输出 0 就好了。
当 m <= n*n 时，可以对于所有可能的 m ，计算 (sum_{i=1}^{n}max(ai,bi)=m) 的方案数然后进行累加。

我们为了保证 max 函数的唯一性，不妨令 ai >= bi 时 max(ai,bi) = ai；ai < bi 时 max(ai,bi) = bi。
考虑 a 中的 i，它要对答案产生贡献，只能和 b 中的 1 ~ i 配对；同样，对于 b 中的 i 要产生贡献，只能和 a 中的 1 ~ i-1 配对。

于是我们可以从小到大，考虑每一个数 i 在 a 序列与 b 序列中是否会对答案产生贡献。我们只需要知道在 i 之前有多少数未被配对。
由于 a 与 b 是一一配对，所以 a 中未配对的元素个数一定等于 b 中未配对的元素个数。
由此自然得出 dp 的状态定义：dp[i][j][k] 表示考虑到 i，i 之前 a/b 中有 j 个数还未被配对，此时凑出的和为 k。

通过分类讨论 a 中的 i 是否有贡献以及 b 中的 i 是否有贡献，得到四类转移。
注意当 a 中的 i 与 b 中的 i 相匹配时，根据上文的讨论 b 中的 i 是没有贡献的。
时间复杂度 O(n^4)。

@accepted [email?protected]

#include<cstdio>
const int MOD = 998244353;
const int MAXN = 50;
int dp[MAXN + 5][MAXN + 5][MAXN*MAXN + 5];
int main() {
    int n,m; scanf("%d%d",&n,&m);
    if( m > n*n ) {
        puts("0");
        return 0;
    }
    int ans = 1;
    for(int i=1;i<=n;i++)
        ans = 1LL*i*ans%MOD;
    dp[0][0][0] = 1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=i;j++)
            for(int k=0;k<=n*n;k++)
                dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k])%MOD;
        for(int j=0;j<i;j++)
            for(int k=i;k<=n*n;k++)
                dp[i][j][k] = (dp[i][j][k] + 1LL*j*dp[i-1][j][k-i]%MOD)%MOD;
        for(int j=0;j<i;j++)
            for(int k=i;k<=n*n;k++)
                dp[i][j][k] = (dp[i][j][k] + 1LL*(j+1)*dp[i-1][j][k-i]%MOD)%MOD;
        for(int j=0;j<i-1;j++)
            for(int k=2*i;k<=n*n;k++)
                dp[i][j][k] = (dp[i][j][k] + 1LL*(j+1)*(j+1)%MOD*dp[i-1][j+1][k-2*i]%MOD)%MOD;
    }
    int res = 0;
    for(int i=m;i<=n*n;i++)
        res = (res + dp[n][0][i])%MOD;
    printf("%lldn",1LL*ans*res%MOD);
}

@[email?protected]

就代码而言写起来还是很愉快的，甚至不足 1kb。

然而我当时好像一不小心把 m ≤ …… 看成 m = …… 不过还好最后改过来了，不然就直接炸掉了。。。