专栏文章

题解：CF403D Beautiful Pairs of Numbers

HHim_shu
CF403D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkt70h
此快照首次捕获于
2025/12/02 04:02
3 个月前
此快照最后确认于
2025/12/02 04:02
3 个月前
查看原文
本蒟蒻的第一篇紫题题解，望管理员过

背景

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

题意

如果整数对序列 (a1,b1),(a2,b2),…,(ak,bk)(a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{k},b_{k}) 满足以下条件，则称其为“美丽序列”：
  • 1≤a1≤b1<a2≤b2<…<ak≤bk≤n1 \leq a_{1} \leq b_{1} < a_{2} \leq b_{2} < \ldots < a_{k} \leq b_{k} \leq n，其中 nn 是给定的正整数；
  • 所有数对长度两两不同。
给定 nn，请你计算长度为 kk 的美丽序列的数量对 10000000071000000007（109+710^{9}+7）取模后的结果。

分析

首先要注意到，因为长度两两不同，敏锐的察觉到，貌似 kk 比较大的时候，貌似答案是 00。
原因：我们全用最小的，1,2,3,…,k1,2,3,\ldots,k 长度有 k×(k+1)/2k \times (k+1) /2，这个是小于 nn 的，而 nn 又是小于 10001000 的，所以 kk 不大于 5050。
故
CPP
if(k*(k+1)/2>n)cout<<"0\n";
接下来我们就可以大胆的设计方法了！
我们考虑 DP。发现只要知道每个块长，块的个数，可以用类似组合的东西解决。
而然对块长设计 DP 简单。
我的 DP 是这样的：
  • 状态：dpi,j,zdp_{i,j,z} 表示有 ii 个序对，序对总长为 jj，最后一个块长为 zz 的方案数。
  • 转移：dpi,j,z=∑k=0z−1dpi−1,j−z,kdp_{i,j,z}=\sum_{k=0}^{z-1}dp_{i-1,j-z,k}
  • 初始：dp0,0,0=1dp_{0,0,0}=1
发现当前的复杂度是 O(k×n3)O(k \times n^3)，明显超时，怎么办？
回答：转移的求和函数可以用前缀和解决，复杂度终于可以在 O(k×n2)O(k \times n^2)，已经可以过了。
这里注意一个小细节如果开 O(k×n2)O(k \times n^2) 的空间不行，要用滚动优化。
无滚动CPP
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;
        }
滚动CPP
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,kn , k 时：
  • 可以把每个块看成一个点，kk 个块就是 kk 个点。
  • 长度为 nn，kk 个块时，相当于有 n−块总长n-块总长 个点中，加入 kk 个点。
  • 明显答案 == ∑z=1nk\sum_{z=1}^{n} k 个块总和为 zz 的方案数 ×(n−j+1)×(n−j+2)×…×(n−j+k)\times (n-j+1) \times (n-j+2) \times \ldots \times (n-j+k)。
  • kk 个块总和为 zz 的方案数是 sm[k][z]sm[k][z]，而乘法可以前缀积解决。
到此完毕。

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...