【BZOJ4361】isn(动态规划,容斥)
规划 动态 容斥
2023-09-11 14:14:41 时间
【BZOJ4361】isn(动态规划,容斥)
题面
题解
首先我们如果确定了一个不降序列,假设它的长度为\(i\),
那么可行的方案数为\(i*(n-i)!\),但是这样有一些非法的情况,即删掉最后一个数之前已经是有序的了。
那么设\(g[i]\)表示长度为\(i\)的不降序列的总数
因为所有长度为\(i\)的不降序列一定包含在长度为\(i+1\)的不降序列之中
如果先构成了一个长度为\(i+1\)的不降序列,再删掉了一位,那么这样是不合法的。
所以长度为\(i\)的不降序列的贡献为:
\[g[i]*(n-i)!-g[i+1]*(n-i-1)!*(i+1)
\]
即先构成了一个长度为\(i+1\)的不降序列,再枚举删去了哪个数构成了长度为\(i\)的不降序列。
至于\(i\)怎么算,可以设\(f[i][j]\)表示以\(i\)结尾,长度为\(j\)的不降序列的个数
\(f[i][j]=\sum f[k][j-1](a[k]\le a[i])\)
树状数组优化一下就好了
时间复杂度\(O(n^2logn)\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define RG register
#define MAX 2002
#define MOD 1000000007
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int a[MAX],n,S[MAX],len;
int f[MAX][MAX],g[MAX];
int c[MAX],jc[MAX],ans;
int lb(int x){return x&(-x);}
void modify(int x,int w){while(x<=len)add(c[x],w),x+=lb(x);}
int getsum(int x){int ret=0;while(x)add(ret,c[x]),x-=lb(x);return ret;}
int main()
{
n=read();jc[0]=1;
for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;
for(int i=1;i<=n;++i)a[i]=S[++len]=read();S[++len]=0;
sort(&S[1],&S[len+1]);len=unique(&S[1],&S[len+1])-S-1;
for(int i=0;i<=n;++i)a[i]=lower_bound(&S[1],&S[len+1],a[i])-S;
f[0][0]=1;
for(int j=1;j<=n;++j)
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;++i)
{
modify(a[i-1],f[i-1][j-1]);
f[i][j]=getsum(a[i]);
add(g[j],f[i][j]);
}
}
add(ans,g[n]);
for(int i=n-1;i;--i)
add(ans,(1ll*g[i]*jc[n-i]%MOD-1ll*g[i+1]*jc[n-i-1]%MOD*(i+1)%MOD+MOD)%MOD);
printf("%d\n",ans);
}
相关文章
- POJ3757 01分数规划
- 0/1背包问题(动态规划)
- 【UOJ#390】【UNR#3】百鸽笼(动态规划,容斥)
- 【UOJ#76】【UR #6】懒癌(动态规划)
- 【CF285E】Positions in Permutations(动态规划,容斥)
- 【CF1132F】Clear the String(动态规划)
- 【BZOJ5471】[FJOI2018]邮递员问题(动态规划)
- 【BZOJ5250】[九省联考2018]秘密袭击(动态规划)
- 【ARC102E】Stop. Otherwise...(容斥原理,动态规划)
- 【BZOJ2839】集合计数(容斥,动态规划)
- 【BZOJ4559】成绩比较(动态规划,拉格朗日插值)
- 【BZOJ1046】上升序列(动态规划,贪心)
- 【BZOJ1030】文本生成器(AC自动机,动态规划)
- 【BZOJ1911】【APIO2010】特别行动队(斜率优化,动态规划)
- 【算法】【递归与动态规划模块】数组字符串转字母的所有种数
- 【BZOJ4922】[Lydsy六月月赛]Karp-de-Chant Number 贪心+动态规划
- 【BZOJ1700】[Usaco2007 Jan]Problem Solving 解题 动态规划
- C#,动态规划(DP)模拟退火(Simulated Annealing)算法与源代码
- 动态规划算法之图像压缩问题
- EXPLAIN - 显示语句执行规划
- PRM路径规划算法
- LeetCode091之解码方法(相关话题:动态规划)
- LeetCode085子矩阵最大累加和(相关话题:前缀和,动态规划)
- 移动机器人 | 全局路径规划
- suseoj 1209: 独立任务最优调度问题(动态规划)
- 西北区域新能源发展规划及运行监管报告:弃光弃风依然严重
- 最佳加法表达式(动态规划)