ABC461

本次赛时三题ABC，补了DEF，D出现的问题是对特殊情况没有判断出来，E题是一道有趣的数据结构题，F是正解是DP，但是数据较弱，特殊的爆搜也是可以过的。
由于时间有限，从本次题解开始我就不再去详细写一些过于简单的题了，只是一笔带过。。。

ABC

A题是基础的比较题。
B题判断映射关系。
C题排序后贪心地选够M个颜色后，再贪心地任意选择剩下的价值更大的东西。

补题

D

问题陈述

有一个 $H \times W$ 网格，每个单元格包含一个整数 $0$ 或 $1$ 。
每个单元格中写入的整数的信息以长度为 $W$ 的 $H$ 字符串 $S_1, S_2, \dots, S_H$ 的形式给出。如果 $S_i$ 的第 $j$ 个字符为“0”，则将 $0$ 写入网格顶部起第 $i$ 行、左侧起第 $j$ 列的单元格中；如果 $S_i$ 的第 $j$ 个字符是“1”，则在该单元格中写入 $1$ 。

求写入的整数之和等于 $K$ 的矩形区域的数量。
更正式地说，找到满足以下所有条件的整数四元组 $(r_1, c_1, r_2, c_2)$ 的个数：

• $1 \le r_1 \le r_2 \le H$
• $1 \le c_1 \le c_2 \le W$
• 在满足 $r_1 \le i \le r_2, c_1 \le j \le c_2$ 的所有整数对 $(i, j)$ 中，写入从上数第 $i$ 行和从左数第 $j$ 列的单元格中写入的整数之和等于 $K$ 。

数据范围是500

分析：

需要求矩阵和恰好等于K的的数量，如果暴力枚举的话复杂度是$O(N^4)$。
但是考虑到数据范围是500，因此我们只需优化到$O(N^3)$即可，也就是优化一个维度。
预处理前缀和可以$O(1)$查询一段区间的和，这样就可以实现一个维度的优化。

思路：

以行为例，处理每一行的前缀和，随后用$O(N^2)$枚举$[l,r]$，固定统计l列到r列这一区间，这样从l列到r列的每一行可以用前缀和$O(1)$求出。
问题转化为了一个序列$A$，其中$A_i=pre_r-pre_{l-1}$，求出序列$A$中区间和等于K的区间。
由于数据非负，可以采用滑动窗口来求，注意连续的0区间即可。（当然用哈希表更加简单且通用）

这里总结一下求区间和等于K的区间数量问题

• 通用解法：哈希表记录前缀和为x的数量，则区间数量=$\sum hash_{K-pre_i}$
• 若数据为正，可以采用简单的双指针法。
• 若数据非负，可以在双指针基础上再增加一个指针用于记录0的区间。

Code

void sol()
{
    int h,w,k;
    cin>>h>>w>>k;
    string s;
    for(int i=0;i<h;i++)
    {
        cin>>s;
        for(int j=0;j<w;j++)
        {
            if(s[j]=='1')mp[i+1][j+1]=1;
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            preh[i][j]=preh[i][j-1]+mp[i][j];
        }
    }
    int ans=0;
    for(int l=1;l<=w;l++)
    {
        for(int r=l;r<=w;r++)
        {
            int tr=1;
            vector<int>sum(h+1,0);
            for(tr=1;tr<=h;tr++)
            {
                sum[tr]=sum[tr-1]+preh[tr][r]-preh[tr][l-1];
            }
            int r1=1,r2=1;
            for(int i=1;i<=h;i++)
            {
                r1=max(r1,i),r2=max(r2,i);
                while(r1<=h&&sum[r1]-sum[i-1]<k)r1++;
                while(r2<=h&&sum[r2]-sum[i-1]<=k)r2++;
                ans+=r2-r1;
            }
        }
    }
    cout<<ans;
}

E

问题陈述

有一个 $N \times N$ 网格。最初，所有单元都被漆成白色。

按给定顺序处理 $Q$ 查询。每个查询都是以下之一：

• 输入 $1$ ：给出一个整数 $R$ 。将网格顶部第 $R$ 行中的所有单元格涂成黑色。
• 输入 $2$ ：给出一个整数 $C$ 。将网格左侧第 $C$ -th 列中的所有单元格涂成白色。

处理完每个查询后，输出该点网格中黑色单元格的数量。

分析：

每次对行涂黑，对列涂白，求黑色格子数量。考虑每次操作对答案的贡献：

• 行涂黑操作：增加涂黑前该行白格子数量
• 列涂白操作：减少涂白前该列黑格子数量

思路：

假设当前时间为$t$，该行上一次涂黑的时间戳为$t_{i-1}$，则该行涂黑前白格子数量为$t_{i-1}$到$t_i$这段时间进行列操作的数量。（当然需要去重）
列操作同理。
至于去重怎么实现？我们只需要记录上一次的操作即可，对该位置再次操作时覆盖上一次的时间即可。

那么我们的需求就是：对时间区间进行操作次数统计，以及对每次询问（即一个新的时间戳），更新该时间对应的操作。实际上就是单点修改+区间查询。因此使用树状数组就可以实现。

Code

int n,q;
vector<int>col(maxn,0),row(maxn,-1);
vector<int>BITcol(maxn,0),BITrow(maxn,0);

inline int lowbit(int x){return -x&x;}
void update(vector<int>&BIT,int pos,int val)
{
    if(pos==0)return;
    for(int i=pos;i<=q;i+=lowbit(i))
    {
        BIT[i]+=val;
    }
}
int sum(vector<int>&BIT,int pos)
{
    int res=0;
    for(int i=pos;i>0;i-=lowbit(i))
    {
        res+=BIT[i];
    }
    return res;
}

void sol()
{
    cin>>n>>q;
    int res=0;
    for(int i=1;i<=q;i++)
    {
        int x,f;
        cin>>x>>f;
        if(x==1)
        {
            if(row[f]==-1)
            {
                res+=n;
                row[f]=i;
                update(BITrow,i,1);
            }
            else
            {
                res+=sum(BITcol,i)-sum(BITcol,row[f]);
                update(BITrow,row[f],-1);
                update(BITrow,i,1);
                row[f]=i;
            }
        }
        else
        {
            res-=sum(BITrow,i)-sum(BITrow,col[f]);
            update(BITcol,col[f],-1);
            update(BITcol,i,1);
            col[f]=i;
        }
        cout<<res<<'\n';
    }
}

F

问题陈述

您将获得一个正整数 $N$ ($N\le 10^{10}$)。
如果满足以下所有条件，我们将非空正整数序列 $A$ 称为好序列：

• $A$ 的所有元素都是不同的。
• $A$ 的所有元素的乘积等于 $N$ 。

序列的分数定义为序列中所有元素的总和。
求所有好序列的分数以 $998244353$ 为模的总和。

分析：

需要一个序列乘积为N，且不重复，显然序列中可能的元素为N的所有因数，因此我们先把N的所有因数求出来并排序成序列$B$，时间复杂度$O(\sqrt{N}\log N)$
先不考虑排序问题
我们需要从$B$中选出j个数，使者j个数乘积为N。
定义$F_{x,j}$：选择j个数且乘积为x的序列数量。
由于在序列$B$中选，且不能重复，因此这是一个01背包问题。
仅需考虑是否选择$B_i$
状态转移方程为：

$$F_{x\times B_i,j}=F_{x\times B_i,j}+F_{i,j-1}$$

由于最终需要统计分数（分数定义为序列中所有元素的总和），因此我们再定义$G_{x,j}$为选择j个数且乘积为x的序列总分数。
在选择$B_i$时，$x\times B_i$分数增加的部分为应该为在$x$的基础上，增加$B_i$和对应区间数量的乘积。
状态转移方程为

$$G_{x\times B_i,j}=G_{x\times B_i,j}+G_(i,j-1)+F_{i,j-1}\times B_i$$

最后再乘以对应区间长度的阶乘即可。

复杂度分析：
实际上由于不能重复，那么一个长度为L的区间最小乘积为$L!$，那么长度就不会超过13，因为$13!\ge 10^{10}$。而根据题解，$N$最多也只有2304个因数。
因此复杂度约为$O(2304\times 2304\times 14)$

一个有趣的解法，暴力深度搜索，直接从小暴力枚举所有可能的因子，保证不重复即可。代码如下

void dfs(int x,int lst,int len,int sum)
{
    ans=(ans+fac[len]*(sum+x)%mod)%mod;
    for(int i=lst+1;i*i<x;i++)
    {
        if(x%i)continue;
        dfs(x/i,i,len+1,sum+i);
    }
}

Code

void sol()
{
    int n;
    cin>>n;
    vector<int>fact,fac(15,0);
    fac[0]=1;
    for(int i=1;i<15;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i)continue;
        fact.push_back(i);
        if(i*i==n)continue;
        fact.push_back(n/i);
    }
    sort(fact.begin(),fact.end());
    int len=fact.size();
    vector<vector<int>>dp(len,vector<int>(15,0));//dp[i][j]表示已经选择了j个数，且乘积为fact[i]的方案数
    vector<vector<int>>sco(len,vector<int>(15,0));//计算分数
    //选上fact[i],dp[idx(fact[i]*fact[k])][j+1]+=dp[i][j]

    //01背包
    dp[0][0]=1;
    for(int i=0;i<len;i++)//考虑加入第i个物品
    {
        int x=fact[i];
        for(int k=len-1;k>=0;k--)
        {
            if(i+k>=len)continue;
            int y=fact[k];
            if(n%(x*y))continue;
            int idx=lower_bound(fact.begin(),fact.end(),x*y)-fact.begin();//显然idx>k
            if(idx>=len)continue;
            for(int j=13;j>=0;j--)
            {
                dp[idx][j+1]=(dp[idx][j+1]+dp[k][j])%mod;
                sco[idx][j+1]=(sco[idx][j+1]+sco[k][j]+x%mod*dp[k][j]%mod)%mod;
                // if(idx==2&&dp[k][j])cout<<k<<' '<<j<<' '<<dp[k][j]<<'\n';
            }
        }
    }
    int res=0;
    for(int i=0;i<len;i++)
    {
        cout<<fact[i]<<": ";
        for(int j=1;j<5;j++)cout<<dp[i][j]<<" \n"[j==4];
    }
    for(int i=1;i<15;i++)res=(res+sco[len-1][i]*fac[i]%mod)%mod;
    cout<<res;
}