[UER#6 C]逃走

やり方
要求されるのは分散であり,実際にはすべての場合に異なる位置を通過する個数と異なる位置を通過する二乗和を求め,d dとd 2 d 2とする.全部で4つの方向ベクトルがあり、任意の歩き方は1つのベクトルシーケンスに対応します.先処理W(i,x,y)W(i,x,y)は、長さがi i iであることと、(x,y)(x,y)であるベクトル系列が何種類あるかを示す.どのようにd dを求めるかは、もちろん簡単です.各座標は明らかに独立して寄与を統計することができ、各座標が初めて通過したときに統計することを望んでいる.g[i]g[i]は長さi iを表し、1≦j≦i 1≦j≦iが前j個のベクトル接頭辞と(0,0)(0,0)を満たすものは存在しないとする.以降、このような場合を単に「接頭辞(0,0)(0,0)が存在しない」と呼ぶ.g[i]=(w 1+w 2+w 3+w 4)i−Σij=1 W(j,0,0)∗g[i]=(w 1+w 2+w 3+w 4)i−Σj=1 iW(j,0,0)∗g[i−j]でd=Σni=0Σ(x,y)W(i,x,y)W(i,x,y)∗g[n−i]d=Σi(x,y)W(x(x,y)W(i,x,y)∗g[n−i]d=0 nΣ(x,y)W(x(y)W(x(x,y)W(x(x,y)W(i,y)W(i,x,y)[n−i]時刻i i iで(x,y)(x,y)に着きました.その後は二度と歩いたことがない.簡単な計算のために,d 2 d 2の意味を変更し,1つの場合,2つの異なる位置(秩序)がいずれも到達した場合,d 2 d 2に1を寄与する.では、本来のd 2 d 2は、新しいd 2 d 2に2 2を乗じてd dを加えることに等しい.同様に,R(i,x,y)R(i,x,y)は長さi,および(x,y)(x,y)を表し,プレフィックス(0,0)(0,0)は存在しないとする.R R Rの計算はまた、R(i,x,y)=W(i,x,y)−Σij=1 W(j,0,0)∗R(i−j,x,y)R(i,x,y)=W(i,x,y)−Σj=1 iW(j,0,0)∗R(i−j,x,x,y)R(i,x,y)=W(i,x,y)=W(i,x,y)−Σj=1 iW(j,0,0,0)∗R(i−j(i−j,x,x,y)そして、S(i,x,y)S(i,x,y)S(i,x,x,y)は長さi,及び(0,(x,y).明らかにS(i,x,y)=Σij=1 W(j,x,y)∗R(i−j,−x,−y)S(i,x,y)=Σj=1 iW(j,x,y)∗R(i−j,−x,−y)はこれらのいくつかを補助し,F(i,x,y)F(i,x,y)F(i,x,y)は長さiのすべての場合を表し,前のjベクトルの和(a,b)(a,b)は初めて到着し,次に、i−j i−j個のベクトルの和が(x,y)(x,y)であり、位置iのとき(a+x,b+y)(a+x,b+y)が初めて到達し、このような2つの異なる位置の総数(したがってxy x yは0ではない)である.ちょっと回り道かもしれません.どうやって手に入れるか考えていますか?F(i,x,y)+=Σij=1 g[j]∗W(i−j,x,y)F(i,x,y)+=Σj=1 i g[j]∗W(i−j,x,y)これは(a,b)(a,b)が初めて到達する総シナリオ数である.(a,b)(a,b)が(a+x,b+y)(a+x,b+y)(a+x,b+y)に到達した後、これ(a+x,b+y)(a+x,b+y)(a+x,b+y)は初めて到達したのではなく、最初の到達(a,b)(a,b)の前に最初に到達したのか、最初の到達(a,b)(a,b)の後に初めて到達したのかを考慮する.F(i,x,y)−=Σij=1 g[j]∗S(i−j,−x,−y)F(i,x,y)−=Σij=1 g[j]∗S(i−j,−x,−y)が最初に(a,b)(a,b)に到達する前に(a+x,b+y)(a+x,b+y)(a+x,b+y)(a+x,b+y)に到達した場合,このスキームを考慮すると,最初に(a+x,b+y)(a+x,b+x,b+y)に到達した後に相当する(a+x,b+x,b+y)a+x,b+y)に,b+x,b+y)に,a+また歩いて帰ってきて、そしてこの途中(a,b)(a,b)を通ります.これには、最初に(a,b)(a,b)に到達する前に(a+x,b+y)(a+x,b+y)に到達したすべてのスキームが含まれているに違いないが、それだけではない.私たちは途中で(a,b)(a,b)を遍歴したが,必ずしも途中で(a,b)(a,b)を遍歴して初めて通過したとは限らない.したがって,1回目の到着(a,b)(a,b)後,1回目の到着(a+x,b+y)(a+x,b+y)を減らし,最後に時刻iで(a+x,b+y)(a+x,b+y)に戻り,途中で(a,b)(a,b)に戻る.F(i,x,y)−＝Σij＝1 F(j,x,y)｛8727｝(W(i−j,0,0)−S(i−j,−x,−y)))F(i,x,y)−−＝Σj＝1 i F(j,x,y)｛W(i−j,0,0)−S(i−j,−x,−x,−x,−y))F(i,x,x,y)−−−−−−−−−−−−Σj＝1 i F(j,x,x,x,y)(W(i−j,0−j,0,0,0)−S(i−S(i−j,−x,−x,−x,−x,−y))))))−1回)(a,b)後の不法案前の式では,1回目の到達(a+x,b+y)(a+x,b+y)から時刻iまでの間に再び(a,b)(a,b)に戻るスキームを減らしたことに注目し,ここでは,このスキーム(すなわちS(i−j,−x,−y)S(i−j,−x,−y)を減らさないために減らす.ではFを得た後,d 2 d 2を簡単に統計できた.d 2=Σni=0Σ(a,b)Σ(x,y)F(i,a,b)∗W(n−i,x,y)d 2=Σi=0 nΣ(a,b)Σ(x,y)F(i,a,b)∗W(n−i,x,y)これで本題は解決する.時間複雑度O(n 4)O(n 4).

#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=220+10,mo=998244353;
int w[5],dx[5]={0,0,0,1,-1},dy[5]={0,-1,1,0,0};
int p1[maxn][maxn][maxn],p2[maxn][maxn][maxn],p3[maxn][maxn][maxn],p4[maxn][maxn][maxn];
int g[maxn];
int i,j,k,l,r,s,t,n,m,x,y,ans,all,d,d2;
int &W(int n,int x,int y){ return p1[x+105][y+105][n]; }
int &F(int n,int x,int y){ return p2[x+105][y+105][n]; }
int &S(int n,int x,int y){ return p3[x+105][y+105][n]; }
int &R(int n,int x,int y){ return p4[x+105][y+105][n]; }
int abs(int x){
    return x<0?-x:x;
}
int main(){
    scanf("%d",&n);
    fo(i,1,4) scanf("%d",&w[i]);
    W(0,0,0)=1;
    fo(i,1,n)
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i)
                    fo(k,1,4)
                        (W(i,x,y)+=(ll)w[k]*W(i-1,x+dx[k],y+dy[k])%mo)%=mo;
    g[0]=1;
    all=w[1]+w[2]+w[3]+w[4];
    t=1;
    fo(i,1,n){
        t=(ll)t*all%mo;
        g[i]=t;
        fo(j,1,i) (g[i]-=(ll)W(j,0,0)*g[i-j]%mo)%=mo;
    }
    fo(i,1,n)
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i){
                    R(i,x,y)=W(i,x,y);
                    fo(j,1,i-abs(x)-abs(y))
                        (R(i,x,y)-=(ll)W(j,0,0)*R(i-j,x,y)%mo)%=mo;
                }
    fo(i,1,n)
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i){
                    fo(j,max(abs(x)+abs(y),1),i-abs(x)-abs(y))
                        (S(i,x,y)+=(ll)W(j,x,y)*R(i-j,-x,-y)%mo)%=mo;
                }
    fo(i,1,n)
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i){
                    if (!x&&!y) continue;
                    fo(j,max(abs(x)+abs(y),1),i)
                        (F(i,x,y)+=(ll)(W(j,x,y)-S(j,x,y))*g[i-j]%mo)%=mo;
                    fo(j,1,i)
                        (F(i,x,y)-=(ll)(W(j,0,0)-S(j,x,y))*F(i-j,x,y)%mo)%=mo;
                }
    fo(i,0,n)
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i) (d+=(ll)W(i,x,y)*g[n-i]%mo)%=mo;
    fo(i,0,n){
        t=0;
        fo(x,-n,n)
            fo(y,-n,n)
                if ((x||y)&&abs(x)+abs(y)<=n-i) (t+=F(n-i,x,y))%=mo;
        fo(x,-n,n)
            fo(y,-n,n)
                if (abs(x)+abs(y)<=i) (d2+=(ll)t*W(i,x,y)%mo)%=mo;
    }
    d2=((ll)d2*2%mo+d)%mo;
    t=1;
    fo(i,1,n) t=(ll)t*all%mo;
    ans=((ll)d2*t%mo-(ll)d*d%mo)%mo;
    (ans+=mo)%=mo;
    printf("%d
",ans);
}