热烈庆祝“CSP-S 2020全国开放赛前冲刺模拟训练题2”圆满结束！！！

感谢大毒瘤颗粒囊的题目。题目还是很不错的，部分分设置的不合理，各种神仙随便 AK ，蒟蒻只能爆零。

不会，下一个。

暴搜代码如下：

#include<bits/stdc++.h>
using namespace std;
struct Num{int a,b;};
Num opt[25];
int l1,r1,l2,r2,cnt;
int dfs(int now,int a,int b,int use)
{
    if(a==0&&b==0&&use%2==0) return 1;
    if(a==0&&b==0) return -1;
    if(now>=20) return 0;
    int tmp;
    tmp=dfs(now+1,a,b,use);
    if(tmp!=0) return tmp;
    tmp=dfs(now+1,a-opt[now].a,b-opt[now].b,use+1);
    if(tmp!=0) return tmp;
    return 0;
}
void solve()
{
    cin>>l1>>r1>>l2>>r2,cnt=0;
    for(int i=l1;i<=r1;++i)
    {
        for(int j=l2;j<=r2;++j)
        cnt+=(dfs(0,i,j,0)>0);
    }
    printf("%d\n",cnt);
}
int main()
{
    opt[0].a=1,opt[0].b=0;
    opt[1].a=-1,opt[1].b=1;
    opt[2].a=0,opt[2].b=-2;
    opt[3].a=2,opt[3].b=2;
    for(int i=4;i<20;++i)
    {
        opt[i].a=opt[i-4].a*(-4);
        opt[i].b=opt[i-4].b*(-4);
    }
    int T;cin>>T;
    while(T--) solve();
}

直接枚举矩形宽度，调和级数的和是 \(O(n\log_2 n)\) 级别的。判重直接用 \(\text{hash}\) 即可。但是题目有一点卡常，我的代码只能跑一半的分。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define Lint long long
const int N=1e6+5;
const Lint MOD1=19260817;
const Lint MOD2=998244353;
string s;int n;
Lint sum1[N],ksm1[N];
Lint sum2[N],ksm2[N];
set<pair<Lint,Lint> > bag;
inline pair<Lint,Lint> cut(int l,int r)
{
    Lint tmp1=(sum1[r]-sum1[l-1]*ksm1[r-l+1]%MOD1+MOD1)%MOD1;
    Lint tmp2=(sum2[r]-sum2[l-1]*ksm2[r-l+1]%MOD2+MOD2)%MOD2;
    return make_pair(tmp1,tmp2);
}
int solve(int len)
{
    bag.clear();
    if(n%len==0&&n!=len)
    {
        for(int i=1;i+len-1<=n;i+=len)
        {
            pair<Lint,Lint> L=cut(1,i-1),R=cut(i+len,n),tmp;
            tmp.first=(L.first*ksm1[n-i-len+1]%MOD1+R.first)%MOD1;
            tmp.second=(L.second*ksm2[n-i-len+1]%MOD2+R.second)%MOD2;
            bag.insert(tmp);
        }
    }
    Lint rem=n%len;
    for(int i=1;i+rem-1<=n;i+=len)
    {
        pair<Lint,Lint> L=cut(1,i-1),R=cut(i+rem,n),tmp;
        tmp.first=(L.first*ksm1[n-i-rem+1]%MOD1+R.first)%MOD1;
        tmp.second=(L.second*ksm2[n-i-rem+1]%MOD2+R.second)%MOD2;
        bag.insert(tmp);
    }
//    printf("%d\n",(int)bag.size());
    return bag.size();
}
Lint res=0;
int main()
{
    cin>>s,n=s.length(),ksm1[0]=ksm2[0]=1;
    for(int i=1;i<=n;++i) ksm1[i]=ksm1[i-1]*27%MOD1;
    for(int i=0;i<n;++i) sum1[i+1]=(sum1[i]*27+s[i]-'a'+1)%MOD1;
    for(int i=1;i<=n;++i) ksm2[i]=ksm2[i-1]*27%MOD2;
    for(int i=0;i<n;++i) sum2[i+1]=(sum2[i]*27+s[i]-'a'+1)%MOD2;
    for(int i=1;i<=n;++i) res+=solve(i);
    printf("%lld\n",res);
    return 0;
}

这道题目感觉还可以，原本应该有机会拿满分的，但是由于考虑到其他题目的部分分，就没打（然后发现部分分还没有这个多）。

就是考虑用 \(f_{i,j,k}\) 表示在第 \(i\) 列搭高度为 \(j\) 的积木时的和，同时 \(k\in {0,1}\) ，表示是否有过高度为 \(h\) 的列。这里的平方和强行用二项式定理来维护。然后转移方程易得：

\[f_{i,j,0}=\sum_{k=1}^{h-1} (f_{i-1,k,0}+max(0,j-k))
\]

\[f_{i,j,1}=\sum_{k=1}^h (f_{i-1,k,1}+max(0,j-k)) (j<h)
\]

\[f_{i,h,1}=\sum_{k=1}^{h-1} (f_{i-1,k,0}+max(0,j-k))+\sum_{k=1}^h (f_{i-1,k,1}+max(0,j-k))
\]

然后这个东西前缀和优化还是比较方便的，然后就可以 \(O(n^2)\) 了。

代码如下， \(O(n^3)\) 的做法：

#include<bits/stdc++.h>
using namespace std;
#define Lint long long
const int N=2e2+5;//woshishabi
const Lint MOD=998244353;
int n,m;
Lint way[N][N][2];
Lint f1[N][N][2];
Lint f2[N][N][2];
int main()
{
    cin>>n>>m;
    for(int j=1;j<m;++j)
    f1[1][j][0]=j,f2[1][j][0]=j*j,way[1][j][0]=1;
    f1[1][m][1]=m,f2[1][m][1]=m*m,way[1][m][1]=1;
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<m;++j)
        {
            for(int k=1;k<m;++k)
            {
                if(j<=k)
                {
                    f1[i][j][0]+=f1[i-1][k][0],f1[i][j][0]%=MOD;
                    f2[i][j][0]+=f2[i-1][k][0],f2[i][j][0]%=MOD;
                    way[i][j][0]+=way[i-1][k][0],way[i][j][0]%=MOD;

                    f1[i][j][1]+=f1[i-1][k][1],f1[i][j][1]%=MOD;
                    f2[i][j][1]+=f2[i-1][k][1],f2[i][j][1]%=MOD;
                    way[i][j][1]+=way[i-1][k][1],way[i][j][1]%=MOD;
                }
                else
                {
                    f1[i][j][0]+=f1[i-1][k][0]+(j-k)*way[i-1][k][0]%MOD,f1[i][j][0]%=MOD;
                    f2[i][j][0]+=f2[i-1][k][0]+2*f1[i-1][k][0]*(j-k)%MOD+way[i-1][k][0]*(j-k)*(j-k)%MOD,f2[i][j][0]%=MOD;
                    way[i][j][0]+=way[i-1][k][0],way[i][j][0]%=MOD;

                    f1[i][j][1]+=f1[i-1][k][1]+(j-k)*way[i-1][k][1]%MOD,f1[i][j][1]%=MOD;
                    f2[i][j][1]+=f2[i-1][k][1]+2*f1[i-1][k][1]*(j-k)%MOD+way[i-1][k][1]*(j-k)*(j-k)%MOD,f2[i][j][1]%=MOD;
                    way[i][j][1]+=way[i-1][k][1],way[i][j][1]%=MOD;
                }
            }
            f1[i][j][1]+=f1[i-1][m][1],f1[i][j][1]%=MOD;
            f2[i][j][1]+=f2[i-1][m][1],f2[i][j][1]%=MOD;
            way[i][j][1]+=way[i-1][m][1],way[i][j][1]%=MOD;
        }
        for(int k=1;k<=m;++k)
        {
            f1[i][m][1]+=f1[i-1][k][0]+(m-k)*way[i-1][k][0]%MOD,f1[i][m][1]%=MOD;
            f2[i][m][1]+=f2[i-1][k][0]+2*f1[i-1][k][0]*(m-k)%MOD+way[i-1][k][0]*(m-k)*(m-k)%MOD,f2[i][m][1]%=MOD;
            way[i][m][1]+=way[i-1][k][0],way[i][m][1]%=MOD;

            f1[i][m][1]+=f1[i-1][k][1]+(m-k)*way[i-1][k][1]%MOD,f1[i][m][1]%=MOD;
            f2[i][m][1]+=f2[i-1][k][1]+2*f1[i-1][k][1]*(m-k)%MOD+way[i-1][k][1]*(m-k)*(m-k)%MOD,f2[i][m][1]%=MOD;
            way[i][m][1]+=way[i-1][k][1],way[i][m][1]%=MOD;
        }
    }
    Lint res=0;
    for(int i=1;i<=m;++i) res+=f2[n][i][1],res%=MOD;
    printf("%lld\n",res);
    return 0;
}

不会，下一个。

暴搜如下：

#include<bits/stdc++.h>
using namespace std;
#define Lint long long
const int N=2e2+5,M=1e5+5;
const Lint MOD=998244373;
int n,m,cnt=0;
vector<int> bag[N];
int mp[N][N],deg[N];
int ord[N];bool used[N];
Lint res=0;
void dfs(int now)
{
    if(now>=cnt)
    {
        int hhh=0;
        for(int i=1;i<cnt;++i)
        {
            for(int j=i+1;j<cnt;++j)
            hhh+=(ord[i]>ord[j]);
        }
        Lint sum=1;
        for(int i=1;i<cnt;++i) sum*=mp[i][ord[i]],sum%=MOD;
        res+=MOD+pow(-1,hhh)*sum,res%=MOD;
        return ;
    }
    for(int i=1;i<cnt;++i)
    {
        if(used[i]) continue;
        used[i]=true;
        ord[now]=i;
        dfs(now+1);
        used[i]=false;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1,x;i<=n;++i)
    {
        scanf("%d",&x);
        for(int j=1;j<=x;++j)
        bag[i].push_back(++cnt);
    }
    for(int i=1,u,v;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        for(int c=0;c<(int)bag[u].size();++c)
        {
            for(int d=0;d<(int)bag[v].size();++d)
            {
                if(bag[u][c]==bag[v][d]) continue;
                mp[bag[u][c]][bag[v][d]]++;
                mp[bag[v][d]][bag[u][c]]++;
                deg[bag[u][c]]++;
                deg[bag[v][d]]++;
            }
        }
    }
    for(int i=1;i<=cnt;++i)
    {
        for(int j=1;j<=cnt;++j)
        {
            if(i!=j) mp[i][j]=-mp[i][j];
            else mp[i][j]=deg[i];
        }
    }
    for(int i=1;i<=cnt;++i)
    {
        for(int j=1;j<=cnt;++j)
        mp[i+cnt-1][j]=mp[i][j];
    }
    dfs(1);
    printf("%lld\n",res);
}