うーむ、あと一歩が詰められず。
https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_g
問題
2次元座標上において、互いに向きが異なる3つのベクトルが与えられる。
原点から始め、いずれかのベクトルの示す相対位置に移動する、もしくはその場にとどまるという作業をK回行う。
その結果止まる可能性のある座標は何通りか。
解法
各ベクトルの移動回数をa,b,cとする。
3つのベクトルをv0,v1,v2とすると0≦a,b,cかつ0≦a+b+c≦Kの範囲でa*v0+b*v1+c*v2が何通りあるかを求めることになる。
単純にa,b,cの組み合わせを考えると、これはComb(K+3,6)に一致する。
しかし座標が2次元のため3つのベクトルは独立ではないので、a,bをいくつかいじるのと、cをいくつかいじるので結果が等しくなるケースがある。
これを求めよう。
a*v0+b*v1+c*v2=a’*v0+b’*v1+c’*v2となるケースを考えると、(a-a')*v0+(b-b')*v1+(c-c')*v2=0となる。
この時、(a-a'):(b-b'):(c-c')の比率は一定となるので、この比をA:B:Cとしよう。
なおA:B:CはGCDが1となるようにする。
A:B:Cは連立方程式を解けば求められる。
さて、そうすると3ベクトルの移動回数がa,b,c回の場合と、(a+A),(b+B),(c+C)回の移動先は等しくなる。
よってそのようなケースを重複分として取り除こう。
(0≦a,b,cかつ0≦a+b+c≦K)の示す領域と(0≦(a+A),(b+B),(c+C)かつ0≦(a+A)+(b+B)+(c+C)≦K)の共通部分を求めComb(K+3,6)から引けばよい。
A,B,Cの符号を反転できることを考えると、
上記は2つの三角錐の共通部分を考えるとわかる。
int Q; ll X[3],Y[3],K; ll mo=998244353; ll AP,AQ; ll BP,BQ; ll modpow(ll a, ll n=mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll hoge(ll v) { if(v<0) return 0; return (v+3)*(v+2)%mo*(v+1)%mo*modpow(6)%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>Q; while(Q--) { FOR(i,3) cin>>X[i]>>Y[i]; cin>>K; AP=X[2]*Y[1]-Y[2]*X[1]; AQ=X[0]*Y[1]-Y[0]*X[1]; BP=X[2]*Y[0]-Y[2]*X[0]; BQ=X[1]*Y[0]-Y[1]*X[0]; if(AQ<0) AP=-AP, AQ=-AQ; if(BQ<0) BP=-BP, BQ=-BQ; ll g=__gcd(abs(AP),abs(AQ)); AP/=g; AQ/=g; g=__gcd(abs(BP),abs(BQ)); BP/=g; BQ/=g; ll AA,BB,CC,G; AA=AP*BQ; BB=BP*AQ; CC=-AQ*BQ; G=__gcd(abs(AA),__gcd(abs(BB),abs(CC))); AA/=G; BB/=G; CC/=G; ll ret=hoge(K); if(abs(CC)<=K && abs(AA)<=K && abs(BB)<=K) { ll C[2]={}; C[AA>0]+=abs(AA); C[BB>0]+=abs(BB); C[CC>0]+=abs(CC); ret-=hoge(K-max(C[0],C[1])); } cout<<(ret+mo)%mo<<endl; } }
まとめ
A,B,Cは求めたけどその後のツメが甘かった。