[CF403D]Beautiful Pairs of Numbers

Beautiful Pairs of Numbers"/>

[CF403D]Beautiful Pairs of Numbers

题意：给定$n,k$，对于整数对序列$\left(a_1,b_1\right),\cdots,\left(a_k,b_k\right)$，如果$1\leq a_1\leq b_1\lt a_2\leq b_2\lt\cdots\lt a_k\leq b_k\leq n$且所有的$b_i-a_i$互不相同，则称这个序列是“美丽的”，求美丽的序列的个数

先转化一下，把每个数对$\left(a_i,b_i\right)$看作一个区间$\left[a_i,b_i\right]$，则题目要求的是$k$个长度不同的区间互不重叠地放置在$[1,n]$的方案数

记$f_{i,j}$表示$i$个长度不同的区间总长为$j$且按长度递增排列的方案数，则$f_{0,0}=1,f_{i,j}=f_{i,j-i}+f_{i-1,j-i}$（可以直接把原方案的每个区间长度$+1$，或者在这个基础上再增加一个长度为$1$的区间）

那么答案是$k!\sum\limits_{i=1}^n\binom{n-i+k}kf_{k,i}$

相当于是枚举所有区间的总长，对于总长为$i$的所有方案（$f_{k,i}$），把区间塞到$[1,n]$后我们还有$n-i$的空隙，相当于计算有$k$个区间和$n-i$个空隙的排列数（$\binom{n-i+k}k$），因为$f$计数的是按长度递增排列的方案数，所以最后乘上$k!$表示任意排列

以上所有的东西（组合数，$f$，答案）都可以预处理出来，然后$O(1)$回答询问即可

不是这样的我没有在刷水题

#include<stdio.h>
typedef long long ll;
const int mod=1000000007,N=1000,K=50;
int fac[1010],rfac[1010],f[60][1010],ans[1010][60];
int mul(int a,int b){return a*(ll)b%mod;}
int ad(int a,int b){return(a+b)%mod;}
int C(int n,int k){return mul(fac[n],mul(rfac[n-k],rfac[k]));}
int pow(int a,int b){int s=1;while(b){if(b&1)s=mul(s,a);a=mul(a,a);b>>=1;}return s;
}
int main(){int i,j,k,t,n;fac[0]=1;for(i=1;i<=N;i++)fac[i]=mul(fac[i-1],i);rfac[N]=pow(fac[N],mod-2);for(i=N;i>0;i--)rfac[i-1]=mul(rfac[i],i);f[0][0]=1;for(i=1;i<=K;i++){for(j=i*(i+1)/2;j<=N;j++)f[i][j]=ad(f[i][j-i],f[i-1][j-i]);}for(i=1;i<=N;i++){for(k=1;k<=K;k++){for(j=k*(k+1)/2;j<=i;j++){ans[i][k]=ad(ans[i][k],mul(C(i-j+k,k),f[k][j]));}ans[i][k]=mul(ans[i][k],fac[k]);}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);if(k>K)puts("0");elseprintf("%d\n",ans[n][k]);}
}

转载于:.html