1 条题解
-
1
题意就是求从开始走步,刚好走到的方案数。
我们先考虑一个位置的移动方案,有一下四种:
我们单独看坐标或者坐标的改变方案,发现有三种,这样我们求排列组合达到目标位置就会很麻烦。
所以考虑一下把坐标顺时针旋转45°(不一定顺时针旋转45°,只要旋转后原坐标轴与旋转后坐标轴夹角为45°即可)。
然后我们将原坐标轴的长度作为单位长度。
这样操作之后我们再看一下移动方案,就变成了:
这样单独看坐标或者坐标的改变方案,就只有两种。
这样就只要在两个坐标轴上求和的排列满足总和为终点的和坐标,两个答案乘起来就好了。
注意:坐标的范围是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
- 上传者