当前位置: 首页 > news >正文

【题解】QOJ 8351 [IOI 2022 中国国家队集训@南京 Day 2] Ruin the legend

QOJ 8351 Ruin the legend

题意

给定一个正整数序列 \(a\) 和一个正整数 \(k\),保证 \(a_i\) 严格单调递增,求有多少长度为 \(n\) 的序列 \(p\) 满足:

  • \(p\) 是一个 \(a\) 重排后得到的序列。

  • 对于任意 \(1\le i< n\)\(|p_i-p_{i+1}|\neq k\)

\(n\le 5000\)

题解

知识点:动态规划。

计数。

\(a_i\) 两两不同,所以满足 \(|a_i-a_j|\)\((i,j)\)\(O(n)\) 级别的,下称这样的东西为一组限制。

假如对于每个上述 \((i,j)\),在 \(i,j\) 之间连一条无向边,组成一张无向图,则会得到若干连通块,且每个连通块都是一条链。

链上元素的顺序是有意义的,相邻两个节点代表的 \(a_i\) 之间的差值都是 \(k\),也就是说所有相邻的两个元素都形成了一组限制。

一种处理出所有链的简单方法就是将 \(a\) 升序排序,其中第一关键字为 \(a_i\bmod k\),第二关键字为 \(a_i\),这样每条链在 \(a\) 中就是连续的一段。

正着做,还是太困难了,考虑求出不合法的方案数。

一种可能的想法是设计 \(g_{i}\) 表示恰好有 \(i\) 个限制不满足的情况下,\(p\) 的方案数。

但这其实和正着做没什么区别,还是非常难,考虑容斥。

\(g_i\) 表示钦定有 \(i\) 个限制不满足,其他随便(也就是说除了钦定之外的限制也可能不被满足)的情况下,\(p\) 的方案数。

那么答案就是 \(\displaystyle \sum_{i=0}^n (-1)^{i} g_i\)

为了求出 \(g_i\),需要设计 dp 状态和转移来计算。

首先肯定是从排序后的 \(a\)\(1\)\(n\) 一步一步推过去。

当位于满足 \(a_i-a_{i-1}=k\)\(i\) 时,\(i\)\(i-1\) 可以形成限制,此时就涉及到了形成或者不形成的决策。

同时,由于限制是带绝对值的,如果 \(a_i-a_{i-1}=k\),则把他们正着排反着排都是可行的,且贡献了两种方式。

\(0\)\(1\) 不可能形成限制,所以赋值 \(a_0=-\infty\)

需要注意的时,对于一个决定和 \(i-1\) 形成限制的 \(i\),如果从 \(i-1\)\(i-2\) 选择形成限制的局面转移过来,则不能将其像上文一样随意排列。

宏观地来看,一条链(不仅可以是上文连出的无向图上的一条完整的链,也可以是其子链)在 \(p\) 上的排列方向是正向和反向,不可能说里面的节点又正又反,这也太抽象了。

所以设计 \(f_{i,j,0/1}\) 表示前 \(i\) 个元素,钦定了 \(j\) 个限制不满足,当前 \(i\)\(i-1\) 选择形成限制(第三维为 \(1\)),或者不形成限制(为 \(0\))的方案数。

有转移:

\[f_{i,j,0}=(f_{i-1,j,0}+f_{i-1,j,1})\times (i-j) \]

\[f_{i,j,1}=2f_{i-1,j-1,0}+f_{i-1,j-1,1} \ (a_i-a_{i-1}=k) \]

关于系数 \((i-j)\) 的含义,如果把之前选择形成限制的 \(k\)\(k-1\) 缩成一个位置的话,就是可以与 \(i\) 交换的位置数,本质上就是生成排列的组合意义。

细心读者可能会对上面这段话存疑,\(i-j\) 代表位置数减去形成的限制数,如果两段重叠(如 \(1,2\)\(2,3\),那么 \(2\) 就不能换了),可以交换的位置数难道不是 \(<i-j\) 的嘛?事实上并不是,仔细琢磨一下,如果有重叠一个位置,那有空出一个位置,两者重叠,还是 \(i-j\)

代码使用了刷表法实现转移。

#include<bits/stdc++.h>
using namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()#define N 5005
#define int long longconst int mod=998244353;int n,k,a[N],f[2][N][2];inline int ng(int x){return x&1?mod-1:1;
}inline void add(int &x,int y){x=(x+y+mod)%mod;
}signed main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;a[0]=-697891;rep(i,1,n){cin>>a[i];}sort(a+1,a+1+n,[](int x,int y){if(x%k==y%k){return x<y;}return x%k<y%k;});f[0][0][0]=1;rep(i,0,n-1){int ns=i&1,nx=ns^1;rep(j,0,i){add(f[nx][j][0],f[ns][j][0]*(i+1-j));add(f[nx][j][0],f[ns][j][1]*(i+1-j));if(a[i+1]-a[i]==k){add(f[nx][j+1][1],f[ns][j][0]*2);add(f[nx][j+1][1],f[ns][j][1]);}f[ns][j][0]=f[ns][j][1]=0;}}int ans=0,ns=n&1;rep(i,0,n){add(ans,ng(i)*(f[ns][i][1]+f[ns][i][0])%mod);}cout<<ans<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=30035

相关文章:

  • 2025年10月磨粉机厂家最新推荐排行榜,超细磨粉机,雷蒙磨粉机,立式磨粉机,高效节能磨粉机公司推荐!
  • 2025年10月七水硫酸锌厂家最新推荐排行榜:专业生产与优质服务的行业首选!
  • 2025年10月气柱袋厂家最新推荐排行榜:专业生产与客户口碑双优之选!
  • 2025年10月抖音推广服务商最新权威推荐榜:专业运营与创意内容助力品牌高效增长!
  • 2025年10月防水连接器定做厂家最新推荐榜单,专业定制与卓越品质信赖之选!
  • 2025年10月浇注型聚氨酯厂家最新推荐排行榜,专业生产与市场口碑深度解析!
  • 2025年10月通风天窗厂家最新推荐排行榜,工业/民用通风天窗,屋顶通风天窗,高效节能通风天窗公司推荐!
  • 深入解析:贝叶斯定理入门:用医学测试案例理解先验、后验、似然和证据概率
  • 2025年10月保洁公司最新权威推荐榜:专业服务与客户口碑之选
  • 2025年10月网络营销推广/媒体投放/全案推广/新媒体营销/全媒体推广/推广代运营最新权威推荐榜单
  • 2025年10月安全光栅厂家最新推荐排行榜,超薄/四级/无盲区/红外/光电/小型/冲床/折弯机/机床安全光栅公司推荐
  • Docker Desktop 挂载目录实际位置
  • 2025年10月掘进机厂家最新权威推荐榜单:高效施工与卓越性能的首选品牌!
  • 2025年10月电源适配器厂家最新推荐排行榜,笔记本电源适配器,手机电源适配器,USB电源适配器公司推荐!
  • 2025年10月彩钢瓦保养厂家最新推荐排行榜,防腐彩钢瓦,隔热彩钢瓦,耐候彩钢瓦公司推荐!
  • 【网络安全】二、入门篇:HTTP 协议进阶 ——GET/POST 常用传参手段详解
  • AI元人文构想:基础理论框架解析2025年10月13日
  • 2025年10月南通婚纱照最新权威推荐榜:创意摄影与贴心服务完美结合!
  • 2025年10月安全光栅厂家最新推荐排行榜,超薄/四级/无盲区/红外/光电/小型/冲床/折弯机/机床安全光栅及传感器公司推荐!
  • 2025 年吸塑纸卡厂家推荐榜:吸塑热压/牙刷/电池/玩具/牙刷烫银纸卡厂家,聚焦环保与品质,帮企业精准选对合作伙伴
  • 2025年10月风机盘管定制厂家最新推荐排行榜:专业定制与优质服务口碑之选
  • 2025年10月液压阀块厂家最新推荐排行榜,专业生产与品质保障的首选!
  • 2025年10月风机盘管厂家最新推荐榜单,中央空调风机盘管,商用风机盘管,家用风机盘管,优质供货厂家推荐!
  • 2025年10月微弧氧化厂家最新推荐排行榜,铝合金/镁合金/黑色/钛合金微弧氧化技术加工公司推荐
  • 2025年10月新型农机带制造厂家最新推荐榜单,专业生产与技术创新引领行业前沿!
  • 2025 年打包带厂家推荐榜:PP/PET/铁皮/轻质打包带厂家,聚焦品质与效率,助力企业优化包装方案
  • 2025年10月七水硫酸锌厂家最新推荐排行榜:专业生产与优质服务的行业佼佼者!
  • 2025年10月TAB拉链厂家最新权威推荐榜:品质与创新并重的行业佼佼者!
  • 2025年10月无弦吉他厂家最新推荐排行榜,智能无弦吉他,便携无弦吉他,专业演奏无弦吉他公司推荐!
  • 2025年10月PP鱼池厂家最新推荐排行榜,环保耐用,养鱼爱好者的首选!