「SWTR-07」IOI 2077

挺 SB 的，要不是我睡过头赛时就切了。

我习惯用 \(C(n,m)\) 表示 \(n\) 个数选 \(m\) 个数的方案。

因为 \(a_i\) 升序，显然按 \([l,k),(k,r]\) 去分。

考虑暴力，然而每种方案数很难算。换个角度，考虑一个数的贡献次数。

挺显然的，假如 \(i\in[l,k)\) 那么就是 \(C(k-l,m-1)\times C(r-k,m)\)，即左右各选 \(m\) 包含这个数的方案数。 \(i \in (k,r]\) 同理。

再考虑 \(a_k\)，显然每种方案都有它。

暴力 Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
ll lrd() {
	ll f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

#define mod 998244353
#define int ll

int fpow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*x%mod;
		x=x*x%mod; y>>=1;
	}
	return res;
}
#define N (int)(2e6+5)
int n,a[N],jie[N],djie[N],sum[N],m;

int C(int n,int m) {
	if(m>n||m<0) return 0;
	return jie[n]*djie[m]%mod*djie[n-m]%mod;
}

int SUM(int l,int r) {
	return (((sum[r]-sum[l-1])%mod)+mod)%mod;
}

signed main() {
	jie[0]=djie[0]=1;
	for(int i=1;i<=(int)(2e6);i++) jie[i]=jie[i-1]*i%mod,djie[i]=fpow(jie[i],mod-2);
	rd(); n=rd(); m=rd(); for(int i=1;i<=n;i++) a[i]=rd(),sum[i]=(sum[i-1]+a[i])%mod;
	int ans=0;
	for(int mmm=1;mmm<=m;mmm++) {
		int l=rd(),r=rd(),k=rd();
		int qwq=(r-l)/2,res=0;
		for(int i=0;i<=qwq;i++) {
			int r1=0,x=C(k-l-1,i-1)*C(r-k,i)%mod; //cout<

显然我们不能枚举 \(m\)，考虑对式子拆开，单独看一个小部分。

假如我们看

\[\dfrac{SUM(l,k-1)\times C(k-l-1,i-1)\times C(r-k,i)}{C(k-l,i)\times C(r-k,i)} \]

发现可以化掉

\[SUM(l,k-1)*i*(k-l) \]

那一切都挺显然的了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
ll lrd() {
	ll f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
void pr(int x) {
	if(x<0) {putchar('-');x=-x;}
	if(x>9) pr(x/10);
	putchar(x%10+'0');
}
const int mod=998244353;
#define int ll

int fpow(int x,int y) {
	int res=1; x%=mod;
	while(y) {
		if(y&1) res=res*x%mod;
		x=x*x%mod; y>>=1;
	}
	return res;
}
#define N (int)(2e6+5)
int n,a[N],sum[N],INV[N],m;

int SUM(int l,int r) {
	return (sum[r]-sum[l-1])%mod;
}

int SUM1(int l,int r) {
	return (r+l)*(r-l+1)%mod*fpow(2,mod-2)%mod;
}

int check(int n,int m) {
	return n>=m;
}

signed main() {
	rd(); n=rd(); m=rd(); for(int i=1;i<=n;i++) a[i]=rd(),sum[i]=(sum[i-1]+a[i])%mod;
	INV[0]=INV[1]=1; for(int i=2;i<=(int)(2e6);i++) INV[i]=INV[mod%i]*(mod-mod/i)%mod;
	int ans=0;
	for(int mmm=1;mmm<=m;mmm++) {
		int l=rd(),r=rd(),k=rd();
		int qwq=(r-l)>>1,res=0;
		int qaq=min(qwq,min(k-l,r-k));
		res+=SUM(l,k-1)*SUM1(0,qaq)%mod*INV[k-l]%mod; res%=mod; 
		res+=SUM(k+1,r)*SUM1(0,qaq)%mod*INV[r-k]%mod; res%=mod;
		res+=(qaq+1)*a[k]%mod; res%=mod;
		res=res*INV[qwq+1]%mod; res=(res%mod+mod)%mod;
	//	cout<
数学

相关

Liquidity Providers 的数学原理

『笔记』组合数学

组合数学练习

【YBTOJ高效进阶 21190】欧拉函数（数学）

北京市第14届大学生数学竞赛本科甲乙组试题及参考解答 北京市第14届大学生数学竞赛本

洛谷 P3711 - 仓鼠的数学题（多项式）

结对编程项目总结-带UI的小初高数学学习软件

大数据数学基础--用python实现微积分 20212311孙佳瑜

【数学】卢卡斯定理

数学软件

数学软件

[总结]多项式类数学相关（定理&证明&板子）

标签

一品网 冀ICP备14022925号-6