2021牛客OI赛前集训营-提高组（第一场）-（重现赛）赛后总结

注：买的去年的题，本地OI赛制，排名按当年的计算。

这次真属于是挂大分了，T1挂了10分，T2想出正解然而0分（没删中间行），状态太差了

A.牛表

最开始看错题了导致没怎么打表，连边就到 $1212$，痛失 $1010$ 分。

其他没什么，构个图跑个 spfa 就好了（比 dijkstra 快 $33$ 倍）。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=2005;
const int MOD=998244353;
vector<pa>G[MAXN];
int inv[MAXN],dis[MAXN],q[MAXN*100];
bool vis[MAXN];
int p,t;
int quick_pow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(long long)ret*a%MOD;
        a=(long long)a*a%MOD,b>>=1;
    }
    return ret;
}
void spfa(int s)
{
    int head=1,tail=0;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q[++tail]=s;
    while(head<=tail)
    {
        int x=q[head++];
        vis[x]=0;
        for(auto i:G[x])
        {
			int y=i.first,z=i.second;
			if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                if(!vis[y]) q[++tail]=y,vis[y]=1;
            }
        }
    }
}
int main()
{
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    cin>>p>>t;
    inv[1]=1;
    for(int i=1;i<p;++i)
        for(int j=max(1,i-17);j<=min(p-1,i+17);++j)
            G[i].push_back({i*j%p,abs(i-j)});
    int ans=0;
    for(int i=1;i<p;++i)
    {
        int mul=quick_pow(t,(i-1)*(p-1));
        spfa(i);
        for(int j=1;j<p;++j)
        {
            if(i==j){mul=(long long)mul*t%MOD;continue;}
            ans+=(long long)dis[j]*mul%MOD;
            if(ans>=MOD) ans-=MOD;
            mul=(long long)mul*t%MOD;
        }
    }
    cout<<ans<<endl;
    //printf("time:%lfs",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

B.牛牛和数组操作

设 $d{p}_{l,r}dp\_\{l,r\}$ 为操作区间 $[l,r][l,r]$ 所需花费的最小牛币。

那么显然有转移方程：$d{p}_{l,r}={}_{k=l}^r\{d{p}_{l,k-1}+d{p}_{k+1,r}+prema{x}_{k-1}+sufma{x}_{k+1}\}dp\_\{l,r\}=\backslash min\backslash limits\_\{k=l\}^r\backslash \{dp\_\{l,k-1\}+dp\_\{k+1,r\}+premax\_\{k-1\}+sufmax\_\{k+1\}\backslash \}$。

设 $cn{t}_{l,r}cnt\_\{l,r\}$ 为操作区间 $[l,r][l,r]$ 花费的最小牛币的方案数，集合 $SS$ 为满足操作区间 $[l,r][l,r]$ 花费牛币最小的切分点。

所以有：$cn{t}_{l,r}=\sum _{k\in S}cn{t}_{l,k-1}\times cn{t}_{k+1,r}\times C_{r-l}^{k-l}cnt\_\{l,r\}=\backslash sum\backslash limits\_\{k\backslash in\; S\}\; cnt\_\{l,k-1\}\backslash times\; cnt\_\{k+1,r\}\backslash times\; C\_\{r-l\}^\{k-l\}$。

解释一下这个转移方程是怎么来的，$cn{t}_{l,k-1}\times cn{t}_{k+1,r}\times cnt\_\{l,k-1\}\backslash times\; cnt\_\{k+1,r\}\backslash times$ 表示选择子区间 $[l,k-1][l,k-1]$ 和 $[k+1,r][k+1,r]$ 的各一种合法排列，就等价于从 $r-lr-l$ 中选 $k-lk-l$ 个位置这些位置子区间 $[l,k-1][l,k-1]$ 的操作，那么剩下的位置就是子区间 $[k+1,r][k+1,r]$ 的操作，不难发现一但选定组合排列一定是定下来的。

由于子区间共 $\frac{n\times (n+1)}{2}\backslash frac\{n\backslash times(n+1)\}\{2\}$ 个，区间平均长度为 $\frac{n}{2}\backslash frac\{n\}\{2\}$，常数很小，足以通过本题。

代码：

#include<bits/stdc++.h>
using namespace std;

#define inv(x) quick_pow(x,MOD-2)
const int MAXN=1005;
const int MOD=998244353;
int a[MAXN],dp[MAXN][MAXN],cnt[MAXN][MAXN],premax[MAXN],sufmax[MAXN],fac[MAXN],inv_fac[MAXN];
int quick_pow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(long long)ret*a%MOD;
        a=(long long)a*a%MOD,b>>=1;
    }
    return ret;
}
int C(int n,int m){return (long long)fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;}
int main()
{
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    int n;
    cin>>n;
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=(long long)fac[i-1]*i%MOD;
    inv_fac[n]=inv(fac[n]);
    for(int i=n-1;i>=0;--i) inv_fac[i]=(long long)inv_fac[i+1]*(i+1)%MOD;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) cnt[i][j]=1;
    for(int len=1;len<=n;++len)
    {
        for(int l=1;l+len-1<=n;++l)
        {
            int r=l+len-1;
            premax[l-1]=0;
            for(int i=l;i<=r;++i) premax[i]=max(premax[i-1],a[i]);
            sufmax[r+1]=0;
            for(int i=r;i>=l;--i) sufmax[i]=max(sufmax[i+1],a[i]);
            dp[l][r]=0x3f3f3f3f;
            for(int i=l;i<=r;++i)
            {
                if(dp[l][r]>dp[l][i-1]+dp[i+1][r]+premax[i-1]+sufmax[i+1]) dp[l][r]=dp[l][i-1]+dp[i+1][r]+premax[i-1]+sufmax[i+1],cnt[l][r]=(long long)cnt[l][i-1]*cnt[i+1][r]%MOD*C(r-l,i-l)%MOD;
                else if(dp[l][r]==dp[l][i-1]+dp[i+1][r]+premax[i-1]+sufmax[i+1]) (cnt[l][r]+=(long long)cnt[l][i-1]*cnt[i+1][r]%MOD*C(r-l,i-l)%MOD)%=MOD;
            }
        }
    }
    cout<<cnt[1][n]<<endl;
    // printf("time:%lfs",(double)clock()/CLOCKS_PER_SEC);   //考场忘删这一行了，痛失100pts
    return 0;
}

C.与巨

首先由 $f_i=f_{i-1}\times 2+1f\_i=f\_\{i-1\}\backslash times2+1$ 有 $\frac{f_i+1}{f_{i-1}+1}=2\backslash frac\{f\_i+1\}\{f\_\{i-1\}+1\}=2$，又因为 $f_1+1=2f\_1+1=2$，得 $f_i=2^n-1f\_i=2^n-1$。

那么 等价于 $i\times c\equiv i(\mathrm{m}\mathrm{o}\mathrm{d}{2}^t-1)i\backslash times\; c\backslash equiv\; i\backslash pmod\{2^t-1\}$，即 $i\times (c-1)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{2}^t-1)i\backslash times\; (c-1)\backslash equiv\; 0\backslash pmod\{2^t-1\}$

设 $c-1=2^p\times xc-1=2^p\backslash times\; x$，那么 $ii$ 一定要是 $2^{t+1-p}2^\{t+1-p\}$ 的倍数。

枚举 $tt$，设 $m=\mathrm{\mid }n\mathrm{\mid },g=t+1-pm=|n|,g=t+1-p$：

1. 则 $[2^t,2^{t+1}-1][2^t,2^\{t+1\}-1]$ 的最高位都是 $tt$.

答案即为：

${\sum }_{x=0}^{2^{t-g}}(2^t+x\times 2^g)\times 2^g\backslash sum\backslash limits\_\{x=0\}^\{2^\{t-g\}\}(2^t+x\backslash times\; 2^g)\backslash times\; 2^g$

$=2^g\times {\sum }_{x=0}^{2^{t-g}}(2^t+x\times 2^g)=2^g\backslash times\backslash sum\backslash limits\_\{x=0\}^\{2^\{t-g\}\}(2^t+x\backslash times\; 2^g)$

$=2^g\times ((x+1)\times 2^t+\frac{(x+1)\times x}{2}\times 2^g)=2^g\backslash times((x+1)\backslash times2^t+\backslash frac\{(x+1)\backslash times\; x\}\{2\}\backslash times\; 2^g)$

2. $t=m-1t=m-1$，要满足 $2^t+x\times 2^g\le n\Rrightarrow x=\lfloor {\displaystyle \frac{n}{2^g}}\rfloor -2^{t-g}2^t+x\backslash times\; 2^g\backslash le\; n\; \backslash Rrightarrow\; x=\backslash left\backslash lfloor\backslash dfrac\{n\}\{2^g\}\backslash right\backslash rfloor-2^\{t-g\}$。

但注意这样答案会多加上 $(2^t+(x+1)\times 2^g-1-n)\times (2^t+x\times 2^g)(2^t+(x+1)\backslash times\; 2^g-1-n)\backslash times(2^t+x\backslash times\; 2^g)$，减掉就行了。

注意这里要特判 $22$ 种情况：

1. $cc$ 为偶数，答案为 $00$。

2. $c=1c=1$，答案为 $\frac{n\times (n+1)}{2}\backslash frac\{n\backslash times(n+1)\}\{2\}$。

代码：

#include<bits/stdc++.h>
using namespace std;

#define inv(x) quick_pow(x,MOD-2)
typedef long long ll;
const int MAXN=1e7+5;
const int MOD=998244353;
int two[MAXN];
char s[MAXN];
ll c;
int quick_pow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(ll)ret*a%MOD;
        a=(ll)a*a%MOD,b>>=1;
    }
    return ret;
}
int main()
{
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    two[0]=1;
    for(int i=1;i<MAXN;++i) two[i]=two[i-1]*2%MOD;
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s %lld",s+1,&c);
        if(c%2==0){printf("0\n");continue;}
        if(c==1)
        {
            int n=0,m=strlen(s+1);
            for(int i=1;i<=m;++i)
            {
                n=(n<<1)+s[i]-'0';
                if(n>=MOD) n-=MOD;
            }
            int ans=(long long)n*(n+1)/2%MOD;
            printf("%d\n",ans);
            continue;
        }
        int m=strlen(s+1),p=0,n=0;
        for(int i=1;i<=m;++i)
        {
            n=(n<<1)+s[i]-'0';
            if(n>=MOD) n-=MOD;
        }
        --c;
        while(c && !(c&1)) ++p,c>>=1;
        int ans=0;
        for(int t=0;t<m-1;++t)
        {
            int g=max(0,t+1-p),x=two[t-g]-1;
            (ans+=((ll)(x+1)*two[t]%MOD+((ll)(x+1)*x/2)%MOD*two[g]%MOD)*two[g]%MOD)%=MOD;
        }
        int t=m-1,g=max(0,t+1-p),x=0;
        for(int i=1;i<=m-g;++i)
        {
            x=(x<<1)+s[i]-'0';
            if(x>=MOD) x-=MOD;
        }
        x=(x-two[t-g]+MOD)%MOD;
        (ans+=((ll)(x+1)*two[t]%MOD+((ll)(x+1)*x/2)%MOD*two[g]%MOD)*two[g]%MOD)%=MOD;
        ans=((ll)ans-((ll)two[t]+(ll)(x+1)*two[g]%MOD-1-n+MOD)*((ll)two[t]+(ll)x*two[g]%MOD)%MOD+MOD)%MOD;
        printf("%d\n",ans);
    }
    return 0;
}

D.矩阵学说

$6060$ 分做法：

枚举矩阵左上顶点 $x,yx,y$，矩阵大小 $kk$，用二维 $STST$ 表 $\mathcal{O}(1)\backslash mathcal\{O\}(1)$ 查询，时间复杂度 $\mathcal{O}(n^3)\backslash mathcal\{O\}(n^3)$。

$100100$ 分做法：

枚举矩阵左上顶点 $x,yx,y$，二分满足 $kk$，用二维 $STST$ 表 $\mathcal{O}(1)\backslash mathcal\{O\}(1)$ 查询，时间复杂度 $\mathcal{O}(n^2\log n)\backslash mathcal\{O\}(n^2\backslash log\; n)$。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1505;
const int MAXM=105;
int a[MAXN][MAXN],lg[MAXN];
bitset<MAXM>st[MAXN][MAXN][11];
int n,m,K;
void init()
{
    for(int k=1;k<=10;++k)
        for(int i=1;i+(1<<k)-1<=n;++i)
            for(int j=1;j+(1<<k)-1<=m;++j)
                st[i][j][k]=st[i][j][k-1]|st[i+(1<<(k-1))][j][k-1]|st[i][j+(1<<(k-1))][k-1]|st[i+(1<<(k-1))][j+(1<<(k-1))][k-1];
}
int query(int x1,int y1,int x2,int y2)
{
    int k=lg[x2-x1+1];
    return (st[x1][y1][k]|st[x2-(1<<k)+1][y1][k]|st[x1][y2-(1<<k)+1][k]|st[x2-(1<<k)+1][y2-(1<<k)+1][k]).count();
}
long long solve(int k)
{
    long long ans=0;
    for(int x=1;x<=n;++x)
    {
        for(int y=1;y<=m;++y)
        {
            int l=1,r=min(n-x+1,m-y+1),ret=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(query(x,y,x+mid-1,y+mid-1)<=k) ret=mid,l=mid+1;
                else r=mid-1;
            }
            ans+=ret;
        }
    }
    return ans;
}
int main()
{
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    for(int i=2;i<MAXN;++i) lg[i]=lg[i>>1]+1;
    cin>>n>>m>>K;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&a[i][j]),st[i][j][0][a[i][j]]=1;
    init();
    cout<<solve(K)-solve(K-1);
    return 0;
}

//后记&总结：本次考试状态极差，前两题看错题了以为不可做，然后还剩 1h 30min 时才只有 20 分，懂题意后猛然醒悟，如果早点读懂题意应该会更从容一点，也不至于挂 110 分。

笔者能力有限，有未述详尽或有误之处，欢迎指正。