【NOI 2017アナログ4.5】デジタルグリッド

タイトル
Description
菁菁堂には数字の格があり、王解体が一番好きな場所です.伝説の中で、この勢いの雄大な数字の格、N行のN列があって、すべての格子の中に1つの数があります.敢えて自分の王解体决定に挑戦するという通过率九十九パーセントのテーマに挑戦する.格子の第1行および第1列はいずれも与えられた:F[k,1]=lk F[1,k]=tk他の格子に対して、繰返し式:F[i,j]=a*F[i,j-1]+b*F[i-1,j]+cを満たし、王解体がF[n,n](mod 100003)を得ることができる場合、通過率は100%に達する.
Input
テーマには複数のテストデータが含まれており、各テストデータは3行を占めています.各試験データのセットについて、最初の行は4つの整数N,a,b,cを含む.2行目はN個の整数を含み、l[1],...,l[N]を表す.3行目はN個の整数を含み、t[1],...,t[N]を表す.
Output
各グループのデータについて、王解体で得られた答えを表す整数を含む行を出力します.
Sample Input
3 0 0 0 0 0 2 0 3 0 4 3 5 2 7 1 4 3 7 4 4 8
Sample Output
0 41817
Data Constraint
10%のデータ:N<=10000 30%のデータ:N<=10000 100%のデータ:N<=20000,a,b,c<=100000,l[1]=t[1],1<=l[k],t[k]<=100000
問題解
まず最初の行と最初の列の数のaを考えてみましょう.b答えへの貢献をpとする(i,j)はCn−in−i+n−jであることを見いだすことができ,a,bの答えへの寄与は非常に求めやすく,次いでcの答えへの寄与を考慮し,素朴な計算方法はΣni=2Σni=2 Cn−in−i+n−j∗an−ibn−j∗cであるべきであり,次いで終点から4/πの傾きを持つ線被覆点毎の寄与とf[i]=(a+b)であることを見いだした.*f[i-1]、この手で遊ぶのは明らかですが、対角線を越えた後、これは私たちの区間を超え始めたことに気づきました.だから、一番上と一番左の1つを減らすたびに、この2つの位置の最初のステップが固定されていることがわかります.だから套路されないで線形の時間内にこの問題を解決することができます(高速べき乗を含まないと)
コードを貼る

const md=1000003;
var
    l,t:array[0..200005]of int64;
    s,b1,a1:array[0..400005]of int64;
    i,j:longint;
    n,a,b,c,x,y,z,ans,tc:int64;
function quickmi(x,y:int64):int64;
var
    p,t:int64;
begin
    x:=x mod md;
    p:=1;
    while y>0 do
    begin
        if y mod 2=1 then p:=(p*x) mod md;
        x:=(x*x) mod md;
        y:=y div 2;
    end;
    exit(p);
end;
procedure work;
var
    pp:longint;
begin
    readln(n,a,b,c);
    s[0]:=1;
    for i:=1 to 2*n do s[i]:=(s[i-1]*i) mod md;
    a1[0]:=1;
    for i:=1 to n do a1[i]:=(a1[i-1]*a) mod md;
    b1[0]:=1;
    for i:=1 to n do b1[i]:=(b1[i-1]*b) mod md;
    a1[n+1]:=quickmi(b,n);
    for i:=1 to n do
    begin
        read(pp);
        if i=1 then continue;
        x:=(quickmi(s[n-2]*s[n-i],md-2)*s[2*n-i-2]) mod md;
        l[i]:=x;
        y:=(b1[n-i]*a1[n-1]) mod md;
        //y:=(quickmi(b,n-i)*quickmi(a,n-1)) mod md;
        x:=(x*y) mod md;
        x:=(x*pp) mod md;
        ans:=(ans+x) mod md;
    end;
    readln;
    for i:=1 to n do
    begin
        read(pp);
        if i=1 then continue;
        x:=l[i];
        y:=(b1[n-1]*a1[n-i]) mod md;
        //y:=(quickmi(b,n-1)*quickmi(a,n-i)) mod md;
        x:=(x*y) mod md;
        x:=(x*pp) mod md;
        ans:=(ans+x) mod md;
    end;
    readln;
    z:=1;
    for i:=1 to n-2 do
    begin
        z:=(z*(a+b)) mod md;
        ans:=(ans+z*c) mod md;
    end;
    for i:=0 to n-3 do
    begin
        z:=(z*(a+b)) mod md;
        x:=(quickmi(s[n-2]*s[i],md-2)*s[n-2+i]) mod md;
        y:=(a1[i]*b1[n-1]);
        y:=y+(a1[n-1]*b1[i]) mod md;
        y:=(y*x) mod md;
        z:=(z+md-y) mod md;
        ans:=(ans+c*z) mod md;
    end;
    ans:=(ans+c) mod md;
    writeln(ans);
end;
begin
    assign(input,'matrix.in'); reset(input);
    assign(output,'matrix.out'); rewrite(output);
    while not eof do
    begin
        ans:=0;
        work;
    end;
    close(input); close(output);
end.