• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

「NOIP2021模拟赛8.20 C」傀儡子 题解

admin

11月 28, 2021

题目大意

「NOIP2021模拟赛8.20 C」傀儡子

在一个二维直角坐标系内,从((0,0))出发,每一步可以选择向上下左右中的一个方向行进一个长度,有(q)次独立的询问,求(k)步后走到((x,y))的方案数

问题解决

考虑每次走可以选择走(x)方向或者(y)方向,然后减一个(k),很难分析问题,想办法将两个量独立开来

我们可以将坐标系旋转(45^o),把坐标扩大到原来的(sqrt{2})倍,然后发现,在旋转之后,每一步就变成将横坐标和纵坐标都改变一,于是(x,y)便是独立的了,这一步很妙

然后可以当做两个问题分别求解

设旋转后的坐标是(x’,y’)显然最后的方案就是

[C_k^{frac{k-x’}{2}} imes C_k^{frac{k-y’}{2}}
]

可以这样来考虑,对于单独一个(x)(y),总共可以走(k)步,其中需要(x’)步走到规定的地方,然后有(k-x’)步是无用的,由于最后要在(x’)处,所以需要反复横跳,也就是有(frac{k-x’}{2})是可以自己分配的,要在(k)步中选(frac{k-x’}{2})步乱走,也就是(C_k^{frac{k-x’}{2}})

然后这道题需要取摸所以在算组合数的时候需要算乘法逆元,这里有一步优化预处理出(n!)的逆元

[n!^{-1} imes n=(n-1)!^{-1}
]

证明如下

[n!=1^{-1} imes 2^{-1} imes… imes (n)^{-1}
]

[(n-1)^{-1}!=1^{-1} imes 2^{-1} imes … imes (n-1)^{-1}
]

所以

[n! imes n=1^{-1} imes 2^{-1} imes… imes (n)^{-1} imes n=(n-1)^{-1}
]

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=998244353;
const int maxn=1e6;
LL Q,Fc[maxn+5],Ni[maxn+5];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
LL QSM(LL a,LL b){
	LL s=1,w=a;
	while(b){if(b&1)s=s*w%TT;w=w*w%TT;b>>=1;}
	return s;
}
LL C(LL x,LL y){
	return (Fc[x]*Ni[y])%TT*Ni[x-y]%TT;
}
int main(){
	freopen("puppet.in","r",stdin);
	freopen("puppet.out","w",stdout);
	Q=read();Fc[0]=1;
	for(int i=1;i<=maxn;i++)Fc[i]=(Fc[i-1]*i)%TT;
	Ni[maxn]=QSM(Fc[maxn],TT-2);
	for(int i=maxn-1;i>=0;i--)Ni[i]=Ni[i+1]*(i+1)%TT;
	while(Q--){
		int k=read(),x=read(),y=read();
		if(((x+y&1)^(k&1))||(x+y>k)){printf("0
");continue;}
		int x_=x+y,y_=x-y;
		printf("%lld
",C(k,k-x_>>1)*C(k,k-y_>>1)%TT);
	}
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。