1 条题解

  • 1
    @ 2023-10-16 2:26:27

    题意就是求从(0,0)(0,0)开始走rr步,刚好走到(x,y)(x,y)的方案数。

    我们先考虑一个位置的移动方案,有一下四种: (1,0)(1,0) (1,0)(-1,0) (0,1)(0,1) (0,1)(0,-1)

    我们单独看xx坐标或者yy坐标的改变方案,发现有1,0,1{1,0,-1}三种,这样我们求排列组合达到目标位置就会很麻烦。

    所以考虑一下把坐标顺时针旋转45°(不一定顺时针旋转45°,只要旋转后原坐标轴与旋转后坐标轴夹角为45°即可)。

    然后我们将原坐标轴的22\frac{\sqrt{2}}{2}长度作为单位长度。

    这样操作之后我们再看一下移动方案,就变成了: (1,1)(1,1) (1,1)(1,-1) (1,1)(-1,1) (1,1)(-1,-1)

    这样单独看xx坐标或者yy坐标的改变方案,就只有1,1{1,-1}两种。

    这样就只要在两个坐标轴上求111-1的排列满足总和为终点的xxyy坐标,两个答案乘起来就好了。

    注意:坐标的范围是int,所以x,y坐标相加的话会爆int,所以要开long long

    代码丑陋,请勿模仿~

    #include<bits/stdc++.h>
    #define mod 998244353
    using namespace std;
    int t,r;
    long long x,y;
    long long ans;
    long long jj[200009];
    long long ksm(long long x,int p){
    	long long ans=1;
    	while(p){
    		if(p&1){ans*=x;ans%=mod;}
    		x=x*x%mod;
    		p/=2;
    	}
    	return ans;
    }
    long long cc(int n,int m){return jj[n]*ksm(jj[n-m]*jj[m]%mod,mod-2)%mod;}
    int main(){
    	scanf("%d",&t);
    	jj[0]=1;
    	for(int j=1;j<=200000;j++)
    		jj[j]=jj[j-1]*j%mod;
    	while(t--){
    		ans=1;
    		scanf("%lld%lld%d",&x,&y,&r);
    		x=abs(x);y=abs(y);
    		if (x+y>r||(r-x-y)%2==1) {printf("0\n");continue;}
    		int m=(r+x+y)/2;
    		ans*=cc(r,m);
    		ans%=mod;
    		m=(r+abs(x-y))/2;
    		ans*=cc(r,m);
    		printf("%lld\n",ans%mod);
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    193
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    215
    已通过
    14
    上传者