【题解】CF#403 D-Beautiful Pairs of Numbers
2024-09-04 15:29:39
这题还挺对胃口的哈哈~是喜欢的画风!回家路上一边听歌一边想到的解法,写出来记录一下……
首先,由于 \(b_{k} < a_{k + 1}\) ,所以我们可以看作是在一个长度为 n 的序列上选择出 k 个不相交的区间使得这 k个区间的长度各不相同。那么我们可以先求出 \(f[i][j]\) 表示选择了 \(i\) 个区间,这 \(i\) 个区间的区间长度总和为 \(j\) 的方案数。然后,我们考虑用这些方案数与序列剩下的长度的划分的方案数共同构成答案。所以我们再求一个 \(g[i][j]\) 表示将 \(j\) 的长度划分成可空的 \(i\) 段的方案数。答案 \(h[k][n]\) 表示在长为 n 的序列上选出了 \(k\) 个不相交,各不相同的区间的方案数。有了 \(f,g\)数组,我们只需要枚举一下选择的区间总长 i,将 \(f[k][i] * g[k + 2][n - i]\) 加到答案中即可。
但是,这样做不是 \(1000^{3}\) 的的吗?实际上,k 的取值范围远不可能到达 1000。由于区间的长度各不相同,我们不难求出当 \(k >= 45\) 的时候答案为 0,并不需要计算。这样,我们就可以在优秀的 \(5e7\) 的复杂度下通过此题~
#include <bits/stdc++.h>
using namespace std;
#define maxn 1010
#define maxm 100000
#define maxk 50
#define mod 1000000007
#define int long long
int N = , lim = , h[maxn][maxn];
int t[][maxk][maxn], f[maxk][maxn], g[maxk][maxn];
int fac[maxm], inv[maxm]; int read()
{
int x = , k = ;
char c; c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} int C(int n, int m)
{
if(n < m || n < || m < ) return ;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
} void pre()
{
fac[] = ; inv[] = inv[] = ;
for(int i = ; i < maxm; i ++) fac[i] = fac[i - ] * i % mod;
for(int i = ; i < maxm; i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = ; i < maxm; i ++) inv[i] = inv[i - ] * inv[i] % mod;
} void Up(int &x, int y) { x = x + y; if(x >= mod) x -= mod; }
void Work()
{
int pre = , now = ; t[pre][][] = ;
for(int i = ; i <= N; i ++)
{
memset(t[now], , sizeof(t[now]));
for(int k = ; k <= lim; k ++)
for(int j = ; j <= N; j ++)
{
t[now][k][j] = t[pre][k][j];
if(k && j - i >= ) Up(t[now][k][j], t[pre][k - ][j - i]);
}
swap(pre, now);
}
for(int i = ; i <= lim; i ++)
for(int j = ; j <= N; j ++)
f[i][j] = t[pre][i][j] * fac[i] % mod;
for(int i = ; i <= lim; i ++) g[i][] = ;
for(int i = ; i <= lim; i ++)
for(int j = ; j <= N; j ++)
g[i][j] = C(i + j - , j); for(int i = ; i <= lim; i ++)
for(int j = ; j < N; j ++)
{
int ret = ;
for(int k = ; k <= j; k ++)
Up(ret, f[i][k] * g[i + ][j - k] % mod);
h[i][j] = ret;
}
} signed main()
{
pre(); Work(); int T = read();
while(T --)
{
int n = read(), K = read();
if(K <= lim) printf("%I64d\n", h[K][n]);
else printf("0\n");
}
return ;
}
最新文章
- android 修改videoview的宽度和高度
- AMBA
- eclipse添加字体
- cordova android platform cordova build 遇到的问题
- ZeroMQ(java)之Router/Dealer模式
- Servlet&;jsp基础:第五部分
- VC远控(二)连接Server端及密码验证
- 《C++ primer》--第9章
- 基于WebForm+EasyUI的业务管理系统形成之旅 -- ParamQueryGrid行、列合并(Ⅸ)
- css渐变/背景
- centos 7 最小安装后 ip配置
- BZOJ_1864_[Zjoi2006]三色二叉树_树形DP
- 解决sqlite 删除记录后数据库文件大小不变
- CCF CSP 201312-2 ISBN号码
- 18-09-13 机器人和服务器之间的ip配置和脚本的重启
- MySQL中的重做日志(redo log),回滚日志(undo log),以及二进制日志(binlog)的简单总结
- zabbix邮件自动预警
- StringTokenizer 的性能看来真的不用担心
- C++中模板的使用
- 【BZOJ1492】【NOI2007】货币兑换