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

【AGC005D】~K Perm Counting(计数抽象成图)

容斥原理。

求出f(m) ,f(m)指代至少有m个位置不合法的方案数。

怎么求?

注意到位置为id,权值为v ,不合法的情况,当且仅当 v = id+k或 v= id-k

因此,我们把每一个位置和权值抽象成点 ,不合法的情况之间连一条边,可以构成二分图。

借用大佬的图。

由此可知,当选了n条边,就恰好n个位置不合法,限制条件是:连的边不能相邻,

把二分图展开成k条链,进行dp。

还是借用大佬ez_lcw的图

由此总共有2n 个点 k 条链,链与链之间无边 互不干涉。

dp(i,j,pd)表示考虑到第i号点, 连了j条边,是否有连接i 到 i-1号点。

转移方程

dp(i,j,0) = dp(i-1,j,0)+dp(i-1,j,1)

dp(i,j,1) = dp(i-1,j-1,0)

则可得f(m) = (n-m)!\times (dp(2n,m,0) + dp(2n,m,1)) 

简单的乘法原理罢了。

ans = \sum _{i = 0} f(m)*(-1)^1

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long fac[4010];
long long dp[4010][4010][2];
int mod = 1e9+7;
int pd[4999];//判断是否为链头 0 表示是头 头不能连接上一个 
int main(){freopen("neverk.in","r",stdin);freopen("neverk.out","w",stdout);cin>>n>>k;fac[0] = 1;for(int i = 1;i <= n;i++){fac[i] = (fac[i-1]*(long long)i)%mod;}int tot = 0;for(int i=1;i<=k;i++){for(int t=0;t<2;t++){for(int j=i;j<=n;j+=k){tot++;if(i!=j) pd[tot]=1;}}}dp[0][0][0] = 1;for(int i = 1;i <= 2*n;i++){for(int j = 0;j <= n;j++){dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1])%mod;if(j&&pd[i]) dp[i][j][1] = dp[i-1][j-1][0];}}long long cnt = 0;for(int i = 0;i <= n;i++){//cout<<fac[n-i]<<" "<<dp[2*n][i][0]+dp[2*n][i][1]<<endl;long long t = fac[n-i]*(dp[2*n][i][0]+dp[2*n][i][1]);t%=mod;//cout<<t<<endl;if(i%2 == 0){cnt = (cnt +t)%mod;}else{cnt = (cnt - t + mod)%mod;}}cout<<cnt;return 0;
}


http://www.mrgr.cn/news/40681.html

相关文章:

  • 爵士编曲:爵士钢琴编写的规律和步骤 关于教程的个人想法 举一反三
  • Java面试必杀技为什么面试官都爱问源码?
  • MacOS配置python环境
  • 数据工程师岗位常见面试问题-3(附回答)
  • Electron应用创建和打包
  • 什么是PRAM及其工作原理
  • 【2022工业3D异常检测文献】BTF: 结合手工制作的3D描述和颜色特征的异常检测方法
  • Web APIs——Dom获取属性操作
  • 嘉立创编辑器中删除自己画的封装
  • 【网络基础】网络常识快速入门知识清单,看这篇文章就够了
  • Flutter调试模式简介
  • 车辆重识别(2021ICML改进的去噪扩散概率模型)论文阅读2024/9/29
  • Unity 3D导航系统一口气讲完!☆⌒(*^-゜)v THX!!
  • 【数学二】一元函数微分学-连续、可导、可微之间的关系
  • 微信小程序中的 `<block>` 元素:高效渲染与结构清晰的利器
  • Why RTSP?RTSP播放器优势探究
  • 认知杂谈74《远离渣女陷阱,拥抱健康情感》
  • 如何选用笔记本进行思路整理
  • 踩坑Resilience4j @Bulkhead二
  • C++继承实例讲解