题解：P11826 [TOIP2024] 奇巧方块

· · 题解

题目传送门

题目分析

一个基本定论是，要使每个 x \times k 的子矩阵中的 0 的数量为奇数，则在一个子矩阵内满足 k \bmod 2 \ne num_1 \bmod 2，其中 num_1 表示该子矩阵内 1 的个数。这里设填有 1 的格子为黑色格子，否则为白色格子。定义黑色格子的编号为该格子在 c 数组中的下标。

由于 n 和 m 特别大，因此不能暴力模拟。这里考虑从 t 入手。

由于所有黑色格子都在一条直线上，所以我们可以把题目先简化成：一条长为 k 的线段在一条直线上运动，求有多少种情况满足 k \bmod 2 \ne num_1 \bmod 2，其中 num_1 的定义同上。

设线段左端点的位置为 a，右端点的位置为 b，则有 1 \le a < b \le n，且 b-a+1=k。设左端点为 a，右端点为 b 的线段为 (a,b)。

注意到，若 a 从位置 i 移到位置 i+1 且线段内部所包含的黑色格子没有变化，也就是没有黑色格子进入线段范围，也没有黑色格子出线段范围。那么此时的状态和移动前是等价的。由于线段每向右移动一个单位情况数就加一，因此可以考虑进行多少次移动。因此，初始时将线段左端点 a 设置在位置 1 处，并设置两个变量 x 和 y，其中 x 和 y 分别存储线段内包含的第一个黑色格子的编号和最后一个黑色格子的编号。这样，我们每次可以进行一次大移动，移动到 x 号黑色格子出了线段范围或 y+1 号黑色格子移动到线段范围之外。我们如果把这次大移动看成多个小移动累加，其中每个小移动移动一个单位。这样，这次大移动中黑色格子数量一直为 y-x+1。那么，具体应如何移动呢？分类讨论。

为了更直观地理解上面说的，下面给出一张图。

如图，所有标有字母的点为黑色格子。设点 A 为位置 3。绿色线段为 (1,5)。此时 x=y=1。绿色线段满足 c_x+1-a < c_{y+1}-b。因此需要大移动一次，将线段左端点移至 4，将线段右端点移至 8。在这次移动中，线段左端点经过了位置 1,2,3，因此线段中只包含一个黑色格子 A 的情况数为 3，如果满足条件，总情况数加 3。蓝色线段 (14,18)。此时 x=y=4。蓝色线段满足 c_x+1-a \ge c_{y+1}-b，因此要进行一次大移动，移为 (15,19)。此时左端点经过了位置 14，因此线段中只包含一个黑色格子 D 的情况数为 1，若满足条件，总情况数加 1。

这样，所有子矩阵中有黑色格子的情况数就计算完成了。设该数为 P。那么，所有子矩阵中含黑色格子的子矩阵的总数有多少呢？显然，我们可以分横纵来算。首先，横向（即列数）的情况可以抽象成一条线段 (m,n)（即原矩阵第 r 行）上有一个小线段长度为 k 在移动，问一共可以有多少个不同的小线段。显然，小线段右端点最小为 m+k-1，最大为 n。因此总数为 n-(m+k-1)+1，即 n-m-k+2。在题目中取 m=1,n=n。因此总数为 n-k+1。纵向（即行数）的情况比较复杂。由于子矩阵必须有一行落在第 r 行上，因此子矩阵第一行不能高于 \max(1,r-k+1)，最后一行不得低于 \min(m,r+k-1)。与横向类似，情况总数为 \min(m,r+k-1)-\max(1,r-k+1)-k+2。因此，含黑色格子的子矩阵的总数 S 为 (\min(m,r+k-1)-\max(1,r-k+1)-k+2) \times (n-k+1)。

如果 k 为奇数，那么所有不含黑色格子的子矩阵一定满足条件，有 (n-k+1) \times (m-k+1)-S。

答案还需加上含黑色格子且满足条件的子矩阵，注意到每一行该种矩阵数量一定，为 P，一共有 \min(m,r+k-1)-\max(1,r-k+1)-k+2 行，因此答案加上 (\min(m,r+k-1)-\max(1,r-k+1)-k+2) \times P。

代码

//十分抱歉，由于本人失误，代码中m和n弄反了
#include<bits/stdc++.h>
#define N 1000001
using namespace std;
long long m,n,a,b,ans=0,x=0,now=0,t,k,r,c[N],jl=-1;
int main(){
    cin>>n>>m>>t>>k>>r;
    for(int i=1;i<=t;i++){
        cin>>c[i];
        if(c[i]<=k){
            jl=i;
        }
    }
    int ye=0;
    if(c[t]!=m){
        c[++t]=m;
        ye=1;
    }
    a=1,b=k;
    int na=1,nb=1+jl;
    if(jl>=1){
        nb--;
    }
    while(b<=m){
        if(ye&&b==m){
            if(jl==0){
                break;
            }
            long long num=nb-na;
            if(num%2!=k%2){
                x++;
            }
            break;
        }
        if(b==m){
            if(jl==0){
                break;
            }
            long long num=nb-na+1;
            if(num%2!=k%2){
                x++;
            }
            break;
        }
        if(jl==0){
            long long num=c[nb]-b;
            if(k%2==1){
                x+=num;
            }
            a+=(c[nb]-b);
            b=c[nb];
            jl=1;
        }
        else if(c[na]-a+1>=c[nb+1]-b){
            long long len=c[nb+1]-b,num=nb-na+1;
            if(num%2!=k%2){
                x+=len;
            }
            int y=0;
            if(c[na]-a+1==c[nb+1]-b){
                y=1;
            }
            a+=(c[nb+1]-b);
            b=c[nb+1];
            if(y){
                na++;
            }
            nb++;
            jl=nb-na+1;
        }
        else{
            long long len=c[na]-a+1,num=nb-na+1;
            if(num%2!=k%2){
                x+=len;
            }
            b+=(c[na]+1-a);
            a=c[na]+1;
            na++;
            jl=nb-na+1;
            if(!jl){
                nb++;
            }
        }
    }
    now=(n-k+1)*(m-k+1);
    long long up=max((long long)1,r-k+1),down=min(n,r+k-1);
    now-=(m-k+1)*(down-up-k+2);
    if(k%2==1){
        ans=now;
    }
    ans+=x*(down-up-k+2);
    cout<<ans;
    return 0;
}