首页 > 其他分享 >Yet Another RGB Sequence

Yet Another RGB Sequence

时间:2022-10-13 18:00:06浏览次数:71  
标签:int 1ll jcinv RGB RG Another now Yet mod

传送门

读题后立马想到容斥:嗯先算由 \(R-K,G-K,B,0\) 构成的方案数,再把 \(K\) 个 RG 插入。这样就 完美 地简化成模型了!

但明显把 \(K\) 个 RG 删掉后剩下的序列可能会合并出新的 RG 。。。

Notice:考虑方案数是否一样需要插入,也要删除。即要证明充分必要性!

于是枚举 \(i\in [0,min(R-K,G-K)]\),计算 RG 数大于等于 \(K+i\) 个的方案数。

这里提供一个可以用来配系数,同时也是证明正确性的方法:

设有恰好 \(K+j\) 个 RG 的方案数为 \(X\),我们在某个 \(i\) 时计算的值包含有 \(C_{K+j}^{K+i}\) 个 \(X\),明显系数不对。

考虑之前的证明时运用 \(\sum_{i=0}^{i<=j} (-1)^i\times C_{j}^{i}\) 的特殊性,那么同样,我们的目标是凑出一个 常系数 \(\times C_{j}^{i}\)。又明显总数确定为 \(K+j\) 了,于是可以得出正确的系数应该为

\[C_{K+j}^{j}\times C_{j}^{i} \]

那么再运用组合基本知识(其实就是取反+改变枚举顺序),变形为

\[C_{k+j}^{K+i}\times C_{K+i}^{i} \]

于是我们就找到了应该补上的系数 \(C_{K+i}^{K}\)

当然,感性理解的话就是 \(K\) 个 RG 和剩余 \(i\) 个 RG 并不完全一样,需要再次计算。

#include<bits/stdc++.h>
using namespace std;
#define N 3000006
const int mod=998244353;
int jc[N],jcinv[N],fu[N];
int power(int x,int c){
	int now=1;
	while(c){
		if(c&1)now=1ll*now*x%mod;
		x=1ll*x*x%mod;c>>=1;
	}
	return now;
}
inline void init(int n){
	jc[0]=1;
	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%mod;
	fu[0]=1;
	for(int i=1;i<=n;++i)fu[i]=fu[i-1]*(-1);
	jcinv[n]=power(jc[n],mod-2);
	for(int i=n-1;i>=0;--i)jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
	return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ans[N];
int main(){
	init(N-1);
	int R,G,B,K;cin>>R>>G>>B>>K;
	int ans=0;R-=K;G-=K;
	for(int i=0;i<=min(R,G);++i){
		ans=(ans+1ll*power(-1,i)*C(R+G-i-i,G-i)%mod*C(R+G-i-i+B,B)%mod*C(R+G-i+B+K,i+K)%mod*C(K+i,i)%mod)%mod;
	}
	ans=(ans+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

当然,若是不用容斥,也可以直接计算。
容易发现,其实随意排列时只需要满足 R 和 G 不连续就好了。
假设是 G 插入含 R 的序列,那么只要把所有 R 跟它下一位合并,捆绑在一起排列,就不会出现 RG 了。

#include<bits/stdc++.h>
using namespace std;
#define N 3000006
const int mod=998244353;
int jc[N],jcinv[N],fu[N];
int power(int x,int c){
	int now=1;
	while(c){
		if(c&1)now=1ll*now*x%mod;
		x=1ll*x*x%mod;c>>=1;
	}
	return now;
}
inline void init(int n){
	jc[0]=1;
	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%mod;
	fu[0]=1;
	for(int i=1;i<=n;++i)fu[i]=fu[i-1]*(-1);
	jcinv[n]=power(jc[n],mod-2);
	for(int i=n-1;i>=0;--i)jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
	return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ans[N];
int main(){
	init(N-1);
	int R,G,B,K;cin>>R>>G>>B>>K;
	int ans=0;R-=K;G-=K;
	ans=1ll*C(R+B,R)*C(R+B+K,K)%mod*C(G+B+K,G)%mod;
	ans=(ans+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

标签:int,1ll,jcinv,RGB,RG,Another,now,Yet,mod
From: https://www.cnblogs.com/Huster-ZHY/p/16789147.html

相关文章

  • AtCoder Beginner Contest 272 G - Yet Another mod M // 随机化
    题目来源:AtCoderBeginnerContest272G-YetAnothermodM题目链接:ABC272G-YetAnothermodM题意给定一个大小为\(N\),元素各不相同的数组\(A\)。求一个数字\(......
  • RGBA与Opacity
    RGBA是一种色彩空间的模型,表示颜色的三维信息。由RGB色彩空间和Alpha通道组成。RGBA代表Red、Green、Blue、和Alpha(通道)。R:0到255间的整数,代表颜色中的红色成分。G:......
  • org.apache.jasper.servlet.TldScanner.scanJars At least one JAR was scanned for T
    在我本地运行项目成功且正常访问之后,需要把项目打成war包并上传到服务器中运行,但是服务器运行却是tomcat启动成功但是项目本身没有启动,且Catania的执行日志也比本地少了一......
  • SPOJ6059 GCDSQF Another GCD Problem 题解
    题目大意给定两个square-freenumber\(A\)和\(B\)(即没有一个素因子的次数达到\(2\)的数)的01表示形式(即将其有无该素因子排列出来,如\(105=3\times5\times7\),则......
  • CF1256E. Yet Another Division Into Teams 题解 单调队列优化dp
    题目链接:https://codeforces.com/contest/1256/problem/E将\(n\)个数分成若干队,每一队至少包含\(3\)个整数,每一队的代价是最大值与最小值只差,求所有队伍代价之和的最......
  • FusionNet:基于稀疏雷达点云和RGB图像的深度图补全
    原文链接:http://arxiv.org/abs/1902.05356v1代码链接:https://github.com/wvangansbeke/Sparse-Depth-Completion主要思想本文提出了一种新的基于RGB图像的稀疏LiDAR点云深度......
  • verilog实现rgb2gray
    前言  项目算法需求,需要将RGB彩色图像转换为灰度图像,算法原理是很简单的,但是对于刚接触FPGA的宝宝来说,进行时序的设计和调试还是不那么容易的,为了省事儿,就按照上一篇中值......
  • 基于关键帧的RGB-D视觉惯性里程计
    论文信息:ChuC,YangS.Keyframe-BasedRGB-DVisual-InertialOdometryandCameraExtrinsicCalibrationUsingExtendedKalmanFilter[J].IEEESensorsJournal,2......
  • YUV420, YUV422, RGB32内存占用
    用R,G,B三原色可以表示所有颜色,每个分量的范围是0-1.我们用一个字节(8bit,2的八次方256)代表一个分量的话,每个分量的范围就是0-255,一个像素有R,G,B三个分量,所以一个像素就占用......
  • 【ACM MM2021】Cross-modality Discrepant Interaction Network for RGB-D Salient Ob
    【MM2021】Cross-modalityDiscrepantInteractionNetworkforRGB-DSalientObjectDetection代码:https://rmcong.github.io/proj_CDINet.html1、研究动机这是来......