EntropyIncreaser 与金字塔

LOJ6676

第二个和第三个矩阵都是蛇形填数，而第一个矩阵是环形的，这启发我们按照第一个矩阵分层考虑。

先考虑 x1=y1=1,x2=y2=nx_1=y_1=1, x_2=y_2=n 时的做法。

设当前的环为从外到内第 aa 个环，则这个环里最小的数 LL 为 4(a−1)(n−a−1)+14(a-1)(n-a-1)+1，最大的数 RR 为 4a(n−a)4a(n-a)，这个可以按每个环里数的个数推导。

先把每个环里左上角的数抠出来，剩下的数的答案就是 ∑i=L+1Ri∗(R+L+1−i)\sum\limits _{i=L+1}^{R} i*(R+L+1-i)，把这个式子拆开得到 (R+L+1)∑i=L+1Ri−∑i=L+1Ri2(R+L+1)\sum\limits_{i=L+1}^Ri - \sum\limits _{i=L+1}^{R}i^2，用平方和公式就可以 O(1)O(1) 算了。

现在我们可以 O(1)O(1) 地算每个环的贡献了，然后开始考虑满分做法。

满分做法跟上面的只有一点不同：环不完整。这个我们可以把环拆成上下左右四部分，每部分被包含的都是连续的一段，处理好上下界就可以套用上面的式子了。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

typedef __int128 i128;
typedef long long ll;
const int P = 1e8;

i128 n, xa, xb, ya, yb;

i128 S1(i128 x);
i128 S2(i128 x);
i128 calc(i128 a, int type);

int main()
{
    ll _n, _xa, _ya, _xb, _yb;
    cin >> _n >> _xa >> _ya >> _xb >> _yb;
    
    n = _n; xa = _xa; ya = _ya; xb = _xb; yb = _yb;
    
    i128 ans = 0;
    for(int a = 1; a <= (n+1)/2; a++)
    {
        i128 sum = 0;
        i128 val = (4*(a-1)*(n-a+1)+1)%P; 
        if(xa <= a && a <= xb && ya <= a && a <= yb)
            (sum += val*val%P) %= P;
        (sum += calc(a, 1)) %= P;
        (sum += calc(a, 2)) %= P;
        (sum += calc(a, 3)) %= P;
        (sum += calc(a, 4)) %= P;
        (ans += sum*a%P) %= P;
    }
    cout << (ll)ans << "\n";
}


i128 calc(i128 a, int type)
{
    i128 L = (4*(a-1)*(n-a+1)+1)%P;
    i128 R = 4*a*(n-a)%P;
    i128 lval = 0, rval = 0;
    i128 tot = n-a*2+1;
    
    if(type == 1)
    {
        if(xb < a or a < xa) return 0;
        if(yb < a+1 or n-a < ya) return 0;
        lval = max(a+1,ya)-a + L-1;
        rval = min(n-a,yb)-a + L;
    }
    if(type == 2)
    {
        if(yb < n-a+1 or n-a+1 < ya) return 0;
        if(xb < a or n-a < xa) return 0;
        lval = max(a,xa)-a   + L+tot-1;
        rval = min(n-a,xb)-a + L+tot;
    }
    if(type == 3)
    {
        if(xb < n-a+1 or n-a+1 < xa) return 0;
        if(yb < a+1 or n-a+1 < ya) return 0;
        lval = n-a+1-min(n-a+1,yb) + L+2*tot-1;
        rval = n-a+1-max(a+1,ya)   + L+2*tot;
    }
    if(type == 4)
    {
        if(yb < a or a < ya) return 0;
        if(xb < a+1 or n-a+1 < xa) return 0;
        lval = n-a+1-min(n-a+1,xb) + L+3*tot-1;
        rval = n-a+1-max(a+1,xa)   + L+3*tot;
    }
    
    i128 tmp1 = (S1(rval)-S1(lval)+P)%P * (L+R+1)%P;
    i128 tmp2 = (S2(rval)-S2(lval)+P)%P;
    
    return (tmp1-tmp2+P)%P;
}

i128 S1(i128 x)
{
    return x*(x+1)/2 % P;
}
i128 S2(i128 x)
{
    return x*(x+1)/2*(x*2+1)/3 % P;
}

「XXOI 2019」惠和惠惠和惠惠惠

LOJ6672

题意相当于在二维坐标系下，一开始在 (0,0)(0,0)，每次可以向右上走，向右走，向下走，且不能低于 xx 轴，在 nn 次操作后，需要到达 (n,0)(n,0)，同时要求恰好触碰 xx 轴 kk 次。（包括开始和结束）

设 f(i,j)f(i,j) 表示走到 (i,0)(i,0) ，触碰 xx 轴 jj 次的方案数，转移为 f(i,j)=∑k=0i−1f(k,j−1)∗f(i−k,2)f(i,j) = \sum\limits _{k=0}^{i-1}f(k,j-1)*f(i-k,2)。初始状态 f(0,1)=1f(0,1)=1，目标状态 f(n,k)f(n,k)。

设 g(n)=f(n,2)g(n) = f(n,2)，考虑另一个东西 h(n)h(n) 表示从 (0,0)(0,0) 走到 (n,0)(n,0) ，不能进入第四象限的方案数。

则有 g(n)=h(n−2)g(n) = h(n-2)，因为开头和结尾必须分别往上和往下。

为了不重不漏地计数，我们只需要枚举除了 (0,0)(0,0) 外第一次触碰 xx 轴的位置即可：

h(n)=h(n−1)+∑i=2ng(i)∗h(n−i)h(n)=h(n−1)+∑i=2nh(i−2)∗h(n−i)h(n)=h(n−1)+∑i=0n−2h(i)∗h(n−2−i)\begin{aligned} h(n) & = h(n-1) + \sum _{i=2}^{n}g(i)*h(n-i) \\ h(n) & = h(n-1) + \sum _{i=2}^{n}h(i-2)*h(n-i) \\ h(n) & = h(n-1) + \sum _{i=0}^{n-2}h(i)*h(n-2-i) \end{aligned}

设 H(x)H(x) 为 hh 的生成函数，则有:

H(x)=xH(x)+x2H2(x)+10=x2H2(x)+(x−1)H(x)+1H(x)=(1−x)±1−2x−3x22x2\begin{aligned} H(x) & = xH(x) + x^2H^2(x) + 1 \\ 0 & = x^2H^2(x) + (x-1)H(x) + 1 \\ H(x) & = \frac{(1-x) \pm \sqrt{1-2x-3x^2}}{2x^2} \end{aligned}

因为要求 H(0)=1H(0) = 1，所以该式应取负号。

考虑 ff 的生成函数，设 f(∗,j)=Fj(x)f(*,j) = F_j(x) ，不难得到 F1(x)=1F_1(x) = 1。

同时有 Fj(x)=(x+x2H(x))∗Fj−1(x)F_j(x) = (x+x^2H(x))*F_{j-1}(x)，所以 Fj(x)=(x+x2H(x))j−1F_j(x) = (x+x^2H(x))^{j-1}。

将 H(x)H(x) 代入得：

Fj(x)=(x+x2H(x))j−1=(x+1−x−1−2x−3x22)j−1=(1+x−1−2x−3x22)j−1\begin{aligned} F_j(x) & = (x+x^2H(x))^{j-1} \\ & = \left( x + \frac{1-x-\sqrt{1-2x-3x^2}}{2} \right) ^{j-1} \\ & = \left( \frac{1+x-\sqrt{1-2x-3x^2}}{2} \right)^{j-1} \end{aligned}

可以用多项式开根和暴力乘的快速幂得到 O(nlog⁡nlog⁡k)O(n \log n \log k) 的做法。

可以用整式递推数列推导式子做到 O(mlog⁡m+m3+nm)O(m \log m + m^3 + nm) 的时间复杂度，其中 m=12m = 12。