题解：CF403D Beautiful Pairs of Numbers

Him_shu · 2025-10-18 11:51:20 · 题解

本蒟蒻的第一篇紫题题解，望管理员过

背景

打 CF duel 会了战败，赛后补的。

题意

如果整数对序列 (a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{k},b_{k}) 满足以下条件，则称其为“美丽序列”：

所有数对长度两两不同。

给定 n ，请你计算长度为 k 的美丽序列的数量对 1000000007 （ 10^{9}+7 ）取模后的结果。

分析

首先要注意到，因为长度两两不同，敏锐的察觉到，貌似 k 比较大的时候，貌似答案是 0。

原因：我们全用最小的，1,2,3,\ldots,k 长度有 k \times (k+1) /2，这个是小于 n 的，而 n 又是小于 1000 的，所以 k 不大于 50。

故

if(k*(k+1)/2>n)cout<<"0\n";

接下来我们就可以大胆的设计方法了！

我们考虑 DP。发现只要知道每个块长，块的个数，可以用类似组合的东西解决。

而然对块长设计 DP 简单。

我的 DP 是这样的：

状态：dp_{i,j,z} 表示有 i 个序对，序对总长为 j，最后一个块长为 z 的方案数。
转移：dp_{i,j,z}=\sum_{k=0}^{z-1}dp_{i-1,j-z,k}
初始：dp_{0,0,0}=1

发现当前的复杂度是 O(k \times n^3)，明显超时，怎么办？

回答：转移的求和函数可以用前缀和解决，复杂度终于可以在 O(k \times n^2)，已经可以过了。

这里注意一个小细节如果开 O(k \times n^2) 的空间不行，要用滚动优化。

::::info[无滚动]

dp[0][0][0]=sum[0][0][0]=1;

for(int j=1;j<N;j++)sum[0][0][j]+=sum[0][0][j-1];

for(int i=1;i<M;i++)
    for(int j=1;j<N;j++)
        for(int z=1;z<N;z++){
            if(z<=j)dp[i][j][z]=sum[i-1][j-z][z-1],
            sum[i][j][z]=(sum[i][j][z-1]+dp[i][j][z])%mod;
        }

:::: ::::success[滚动]

sum[0][0][0]=1;

for(int j=1;j<N;j++)sum[0][0][j]+=sum[0][0][j-1];

for(int i=1,p=1;i<M;i++,p^=1)
    for(int j=0;j<N;j++){//注意j要从0开始，主要作用是清空sum,我因这个调了0.5 hours+
        sum[p][j][0]=0;
        for(int z=1;z<N;z++){
            sum[p][j][z]=sum[p][j][z-1];
            if(z<=j){
                int x=sum[p^1][j-z][z-1];//用x代替dp
                sum[p][j][z]=(sum[p][j][z]+x)%mod;
                sm[i][j]=(sm[i][j]+x)%mod;//后面计算要用，sm[i][j]表示用i个块总和为j的方案数
            }
        }
    }

:::: 接下来我用滚动讲解。

接下来是答案该怎么算的问题了。

在输入为 n , k 时：

可以把每个块看成一个点，k 个块就是 k 个点。
长度为 n，k 个块时，相当于有 n-块总长个点中，加入 k 个点。
明显答案 = \sum_{z=1}^{n} k 个块总和为 z 的方案数 \times (n-j+1) \times (n-j+2) \times \ldots \times (n-j+k)。
--- 到此完毕。

Code

#include<bits/stdc++.h>
using namespace std;
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define int long long
const int N=1005,M=45,inf=1e16,mod=1e9+7;
int qpow(int a,int b=mod-2){a=(a%mod+mod)%mod;int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
int sum[2][N][N],sm[M][N];
int ans[N][M];
int f[N*2],fav[N*2];
void init(){
    sum[0][0][0]=f[0]=fav[0]=f[1]=fav[1]=1;

    for(int i=2;i<N*2;i++)f[i]=f[i-1]*i%mod,fav[i]=fav[i-1]*qpow(i)%mod;//前缀积预处理

    for(int j=1;j<N;j++)sum[0][0][j]+=sum[0][0][j-1];

    //上面已经给出，不在接受
    for(int i=1,p=1;i<M;i++,p^=1)
        for(int j=0;j<N;j++){
            sum[p][j][0]=0;
            for(int z=1;z<N;z++){
                sum[p][j][z]=sum[p][j][z-1];
                if(z<=j){
                    int x=sum[p^1][j-z][z-1];
                    sum[p][j][z]=(sum[p][j][z]+x)%mod;
                    sm[i][j]=(sm[i][j]+x)%mod;
                }
            }
        }
    //按照我的即可
    for(int n=1;n<N;n++)
        for(int k=1;k<M;k++)
            for(int j=1;j<=n;j++)
                ans[n][k]=(ans[n][k]+sm[k][j]*f[n-j+k]%mod*fav[n-j]%mod)%mod;
}
void work(){
    int n,k;
    cin>>n>>k;
    if(k*(k+1)/2>n)cout<<"0\n";
    else cout<<ans[n][k]<<"\n";
}
void clear(){}
signed main(){
    init();
    int _=1;cin>>_;
    while(_--)clear(),work();
    return 0;
}