2025CCPC哈尔滨站

max67 · 2025-11-13 22:48:14 · 生活·游记

DAY -2

第一次做有摆渡车和转点的飞机（

哈尔滨感觉很开阔啊，马路大大的；过马路时神秘的红绿灯并不能帮助你什么（

晚上去搓了一顿牛锅和羊锅，不过感觉还是饺子最好吃；见到了来自北方的神秘饮料大窑：

这罐吴京代言的液体应该叫（___）

吃完以后去参观了一下中央大街。长长的一条路，上面铺满了独特面包石。虽然还是商业街，但俄罗斯风格的建筑和现代元素混合起来还是有种别样的美感。

感觉去的时候应该买根冰棍边走边吃，哈尔滨虽然很冷但是穿的厚的话身体内部不容易散失热量，这时候吃根冰棍感觉就很快乐。

不过没什么购买欲望就买了些吃的。买的格瓦斯饮料可以直接放房间外不用担心隔夜坏掉了了QAQ。

晚上用熟悉了一下用手柄玩艾尔登法环，感觉这背键映射还是逊逊的，虽然说 steam 有很多关于手柄按键的设置，但不是精英手柄背键不在steam中背键QAQ。

DAY -1

下雪了QAQ。既然雪会化成水，那么为什么下雨要打伞和下雪却不用呢QAQ。

又能见到雪太感动了。

中午跟队长进了哈工大。哈工大太大了，还有校园巴士…或者说杭电太小了。

路上没几个人，后来发现哈工大的楼大约构成一些连通块，都在内部赶路。

不过哈工大内没有共享单车，电瓶车和自行车也很少，不是很懂。

领了袋子，里面塞了个红肠伴手礼，之后去食堂吃饭，喝了神秘的果味奶，感觉食堂比杭电逊一点。

由于 ll 没来，学长整了个活（

下午打了热身赛，发现自己一个题不会，怎么回事呢。队友写了四题。

赛前在远处看了看许久不见的hzy。一队的 hezlik 在和老同学 froggy 聊天，我是社恐就没敢凑上去（

由于是社恐，队友出去跟网友吃饭了，晚上就在补工科数学分析作业（

DAY 1

比赛前发现可以任意带吃的和喝的，感觉有点亏了；赛时才发现热身赛有的 vscode 中的 vim 插件被删掉了，有点难过（

四处望了望，发现昨天和杭电一队一起聊天的队伍的一个人穿上了女装。第二次亲眼看到，感觉有点震撼。

比赛开始，看看 A 题，看了 10 分钟感觉不会。队长过来一盯秒了。其中帮队长调了 L 题。

然后听队友讲了一个字符串题的想法，然后搜寻了一下过了题，决定看 H。感受了 10 分钟开始编 DP。

大约过了一个小时，轮到我的机时了，花半小时把 F 拍上去并调了调，发现跟样例对不上，手模发现也对不上。然后紧急下机思考。

思考了差不多一个半小时，感受出来这样做是有问题的，但我并没有感受出来为什么有问题，所以在一直感受。

然后队友过来一听说我感受出来不对的地方确实不对，但我不知道这地方为什么不对就卡住了。

然后队友开始修我的做法，我在感受我的做法。修好了之后让我拍上去，拍到一半我觉得他说有细节不大对，结果被遗憾赶下机让队友写。在旁边帮助队友最后在半个小时左右过了（

所以整场我只贡献了 0.5 个题（

比完后乱逛。由于没有认识的网友，所以跟高中同学聊了聊天，队友由于是社牛去找呆呆鸟了，蹭了个多的蛇蛇玩偶回来（

看了一眼最终榜，发现北航的队为了搞心态在过题后又故意交了一发（

晚上品尝了波特曼西餐厅，菜式还是和平常大商场里的不同的。尝了奶油蘑菇汤，感觉怪怪的。

DAY 2

虽然哈尔滨路大，但还是很堵，体验到了人生第一次迟运（

补题

由于 QOJ 还没有放题解，这里先放一份

只写我看过和补过的题。由于本场比赛只贡献了 0.5 题，所以会有点少…

H

显然我们不可能记录出所有可能状态，必定要对一些状态进行压缩。注意到最终状态有且仅有一个集合（设为 x）有 2m 个数，这提醒我们若确定了集合 x，我们在转移时只需知道在 x 集合内的数的数量即可。这样状态就被压缩成 O(n) 个。

那么设 dp_i 表示最终集合 x 目前拥有 i 个数，从当前状态到结尾状态的期望长度。

但我们注意到一件事，我们不允许某个时刻集合 x 内有 0 个数，这样的话在以后转移中 x 内永远只有 0 个数，就不合法了。那么如果你把 dp 方程手撕出来的话，会发现有时右边转移的概率之和并不为 1。那么由于一部分的路径所对应的概率并没有被定义，并没有在 dp 方程中体现出来，所以这是不完备的。

那么我们考虑换一个方向进行 dp，设 f_i 表示从起始状态到当前状态，拥有 i 个数的路径的概率和（对于每个起始节点，出去的所有路径的概率和为 1。由于有多个起点路径，所以 f_i 可能会大于 1），g_i 表示从起始状态到当前状态，拥有 i 个数的期望长度。由于所有路径都被考虑到了，所以并不会像上面一样挂掉。

那么 f_i=\sum_{i=1}^{n}[存在一个集合的个数为 i]+\sum_{j}p_{j,i}\times f_j，这个意思是可以选一个起始节点开始或从上一个节点转移过来。g_i=\sum_{j}p_{j,i}\times (f_j+g_j)，这个意思是对于最后一条边是 (j,i) 的路径，这些路径的期望为从 j 结束的路径期望加上 (j,i) 这条边的期望。由于转移可能有环，那么高斯消元一下就好了。

• 当上一个字符为 3 时
  • 我们要找到 3 后面的第一个元素 j，使得 s_j=1，那么由于 3 可以删除任意个相邻元素，那么让 s_j 与 c 匹配即可。
• 当上一个字符不为 3 时
  • 当 s_{i+1}=s_{i}=1 时，我们直接让 s_{i+1} 与其匹配，跳到到 s_{i+1} 即可。
  • 当 s_{i}=1,s_{i+1}=2 时，若我们没有 3，显然 s_{i+1} 我们没有手段处理，这时候就无解了；当我们有 3 时，我们考虑下一个字符为 1 的且长度大于 i 所在段的段（找不到就无解了），通过类似上面平移的思想，我们可以把 i 所在段的所有匹配元素转移到下一个与字符相同的段。设转移后最后一个匹配的位置为 j，那么让 s_{j+1} 与 c 匹配即可。（因为对于一个段，我们显然匹配的位置是一个段的前缀，若长度严格递增，那么一定能匹配到）
  • 当 s_{i}=2,s_{i+1}=1 时，我们让 s_{i+1} 与 c 匹配即可。
  • 当 s_{i}=2,s_{i+1}=2 时，无解。
  • c=3
• 当 i 所在段后至少还有一个段才有解。设后一个段的开头为 j，2
• 当 i+1<j，我们可以操作 s_{j-1},s_{j} 来生成一个 3，然后把 s_{i+1}..s_{j-2} 的元素用 3 吞掉。我们设 3 匹配了 j
• 当 i+1=j，我们设 j 所在段的后一个段的段首为 k，那么同理，3 匹配了 k。

考虑哪些位置可以成为答案：

• 如果没有出现过 3 字符，那么要求最后一个匹配的位置要在最后一段中
• 如果出现过 3 字符
  • 如果最后一个是 3 字符，那么显然可以匹配。（把 3 后的字符全部删即可）
  • 如果最后一个不是 3 字符，那么最后一个字符要和结尾段的字符相同。 （可以通过平移实现。如果不同的话一定不能成为答案）

由于每个串 t 在自动机上唯一有一个位置，所以上面的答案统计并没有重复。

注意到上面有部分过程可以压缩，下面给出我的对着数据拟合出来的 DP 作为参考：

• 设 f[i][0/1] 表示已经匹配了 s 的前 i 段字符，且没有出现过 3，第 i 段至少有一个匹配的元素，第 i 段匹配的元素数量小于段长/等于段长的串 t 数量。

（假设有个 3 匹配的是第 i 段的段首，那么当第 i-1 段匹配的数量为 0，且 i-2 段匹配长度小于段长时，我们实际上应该让 3 匹配第 i-1 段的段首。所以我们应该分为 f[i][0/1] 来计算 ）

• 设 g[i][0/1] 表示已经匹配了 s 的前 i 段字符，且出现过至少一个 3，第 i 段至少有一个匹配的元素，第 i 段匹配的元素数量小于段长/等于段长的串 t 数量。

那么考虑第 i 段的转移：

（设第 i 段的长度为 a_i，字符为 c_i）

• 塞一个 1/2。
  • 从 i-1 段转移到第 i 段时，我们在 t 中加入 1 到 a_i-1 个 c_i 转移到 f/g[i][0]，加入 a_i 个 c_i 转移到 f/g[i][1]。
  • 有 3 的情况下，考虑上面自动机中平移时：设去掉 t 最后一段 c_i 时匹配到了第 j 段，那么应该从第 j（j<i-2,2\nmid i-j） 段转移到第 i 段，加入的 1 的数量要保证大于 i-2 段的段长，否则就不是放在第 i 段了，那么还是分 g[i][0/1] 转移。
• 塞一个 3
  • 那么先考虑 3 匹配的位置是第 i+1 串的开头的数量：满足第 i 段的匹配数量小于段长（留出至少一个位置用于合成 3）的数量为 f[i][0]+g[i][0]，若第 i 段的匹配数量为 0，那么第 i-1 段的匹配数量必须是段长，即 f[i-1][1]+g[i-1][1]。设这个值为 val。
  • 若 i+1 的段长为 1，那么经过操作后 i+1 段的所有元素都被匹配，因此转移到 g[i+1][1]。否则转移到 g[i+1][0] 表示当前这一段只匹配了一个数 3。
  • 注意到上面的操作能够转移 3 后接一段 c_{i+2} 在接其他东西的情况，但是若后面接一段 c_{i+1} 的情况由于我们在上面的第二种情况下找不到字符串 t 砍掉这段 c_{i+1} 后的位置（我们放在了 i+1 段，但想要按照上面的方式被转移到的话得放在第 i 段），所以我们得特殊转移。
  • 枚举转移到第 i+1+2k 的贡献，注意特判第 i+1,i+3 段的转移，因为 i+1 段已经被 3 用掉一个匹配了。
• 在当前段与第 n 段的字符相同时记录一下；在与第 n 段字符不同的段且末尾只有一个 3 的情况会被漏掉，转移的时候统计一下即可。

下面给出代码供参考（注释掉的是优化成 O(n) 的代码，把 O(n^2) 的瓶颈代码替换掉即可）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100,mod=1e9+7;
int n,a1;
int f[N][2],g[N][2],h[N];
int a[N];
void solve()
{
    cin>>n>>a1;
    for(int i=1;i<=n;i++)cin>>a[i],f[i][0]=f[i][1]=g[i][0]=g[i][1]=h[i]=0;
    f[0][1]=1;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        (f[i][0]+=(f[i-1][0]+f[i-1][1])*(a[i]-1))%=mod;
        (f[i][1]+=(f[i-1][0]+f[i-1][1]))%=mod;
        (g[i][0]+=(g[i-1][0]+g[i-1][1])*(a[i]-1))%=mod;
        (g[i][1]+=(g[i-1][0]+g[i-1][1]))%=mod;
        //if(i>2)(h[i]+=h[i-2]+g[i-3][0]+g[i-3][1])%=mod;
        //if(i>2&&a[i]-a[i-2])(g[i][0]+=h[i]*(a[i]-a[i-2]-1))%=mod,(g[i][1]+=h[i])%=mod;
         if(i>2&&a[i]-a[i-2])for(int j=1;j<i-2;j++)if((i-j)&1)
         {
             (g[i][0]+=(g[j][0]+g[j][1])*(a[i]-a[i-2]-1))%=mod;
             (g[i][1]+=(g[j][0]+g[j][1]))%=mod;
         }
        int val=(f[i-1][1]+g[i-1][1])%mod;
        (val+=(f[i][0]+g[i][0]))%=mod;
        if(i<n)
        {
            (g[i+1][a[i+1]==1]+=val)%=mod;
            if(a[i+1]>1)(g[i+1][0]+=(a[i+1]-2)*val)%=mod,(g[i+1][1]+=val)%=mod;
            (g[i+3][0]+=(a[i+3]-a[i+1])*val)%=mod;
            (g[i+3][1]+=val)%=mod;
            //(h[i+5]+=val)%=mod;
             for(int j=i+5;j<=n;j+=2)
                 if(a[j]>a[j-2])(g[j][0]+=(a[j]-a[j-2]-1)*val)%=mod,(g[j][1]+=val)%=mod;
            if((n&1)!=((i+1)&1))(ans+=val)%=mod;
        }
        if((n&1)==(i&1))(ans+=g[i][0]+g[i][1])%=mod;
    }
    cout<<(ans+f[n][0]+f[n][1])%mod<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int _;cin>>_;while(_--)solve();
    return 0;
}

感觉理清楚之后还是很简单的，重点在建自动机。

C

逐个考虑每个问题怎么做：

• Sequence Covering Problems

一个显然的想法是对原序列做差分把区间减转化为单点修改。设 q_i=a_i-a_{i-1}，取 a_1=a_{n+1}=0，操作即选 l\in [1,n],r\in [l,n+1]，q_l\to q_{l}-1 且代价为 b_l，q_r\to q_{r}+1 且代价为 c_{r-1}。为了方便描述我们把 c 数组和 e 数组向右移一位，那么就变成了：q_r\to q_{r}+1 且代价为 c_r。

我们发现由于 b_i,c_i\ge 0，那么我们显然只会令 q_i>0 的位置减 1，q_i<0 的位置 +1，且这是下界。由于 a_1=a_{n+1}=0，那么 \sum[q_i>0]q_i=\sum[q_i<0]|q_i|，即我们每次选一个 q_i>0 和 q_j<0 的位置操作刚好能操作完使得所有 c_i=0。且因为 a_j\ge 0，则 \sum_{i=1}^{j}c_i\ge 0，那么同括号匹配就能构造出来。

那么最小值就是 \sum_i [q_i>0]q_ib_i +[q_i<0]|q_i|c_i

• Many Sequence Covering Problems

若我们对 b_i 加了 1，那么贡献就是 [q_i>0]q_i，显然若这个值大于 d_i，我们可以不断增加 d_i 来获得 +\infin。否则的话不如不操作。

那么如果存在 [q_i>0]q_i>d_i 或 [q_i<0]|q_i|>e_i，那么答案是 +\infin，否则答案同第一问

Many Many Sequence Covering Problems

首先观察一下我们只需要算出不为 +\infin 的方案数和贡献和，由于总的方案数比较好算，那么就能通过容斥算出为 +\infin 的方案数。

那么我们设 f[i][j] 表示前 i 个数，第 i 个数取到 j 的方案数，g[i][j] 表示贡献和。考虑从 i-1 个位置是 j，第 i 个位置是 k 的贡献。下面以 j<=k 的情况为例（要满足 -a_i\ge k）

记 f(i) 为 [i\ge 0]+ [i<0](-i+1)，即值为 i 时的可取区间大小，g(i)=[i\ge 0]i+[i<0](-i)\times (-i+1)/2，即可取区间之和。

• 考虑 f[i][k] 的转移，那么 b,c,e 无关，可以任意取值，且 d 的取值要满足 d\ge k-j。那么记 P=f(b_i)\times f(c_i)\times f(e_i)，若　d_i\ge k-j，那么是 f[i-1][j]\times P\to f[i][k]；若 d_i<0 且 |d_i|\ge j-k，那么是 f[i-1][j]\times P\times (|d_i|-k+j+1)\to f[i][k]。

• 考虑 g[i][k] 的转移，像概率 DP 一样分 (i-1,j)\to(i,k) 这条边的贡献和 g[i-1][j] 的贡献来算。对于 g[i-1][j] 的贡献，转移同上面的分类讨论，下面来谈论这条边的贡献和：显然 c,e 取值无关，对于每一个可以取到的 b，这条边的贡献都为 (k-j)\times b， 那么总的贡献就是 g(b_i)\times (k-j)。 d 还是要满足上面的取值。那么记 P_1=g(b)\times f(c)\times f(e)，若 d_i\ge k-j，那么贡献为 f[i-1][j]\times P\times (k-j)\to g[i][k]；若 d_i<0 且 |d_i|\ge j-k，那么 f[i-1][j]\times P\times (k-j)\times (|d_i|-k+j+1)\to g[i][k]。

显然上面暴力转移的复杂度为 O(n^3)，考虑固定 k 来计算所有贡献到 k 的答案和：

对 j 的取值限制为：j \le |d_i|+k，对于每个 f[i-1][j]，他的贡献系数都是一个关于 j 的零次/一次/二次多项式。那么暴力维护 f[i-1]\times j^k 的取值即可。代码实现有点勾巴。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=5010;
int n;
int a[N],b[N],c[N],d[N],e[N];
int f[N][N],g[N][N];
//前 i 个元素，第 i 个元素是 j 的合法方案数/答案和
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    a[0]=a[n+1]=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    //a[i]-a[i-1] ->b[i]
    //-(a[i]-a[i-1]) ->c[i]
    for(int i=1;i<=n;i++)cin>>c[i+1];
    for(int i=1;i<=n;i++)cin>>d[i];
    for(int i=1;i<=n;i++)cin>>e[i+1];
    f[0][0]=1;
    auto calc1=[&](const int&x){return x>=0?1:(-x+1);};
    auto calc2=[&](const int&x){return x>=0?x:-x*(-x+1)/2%mod;};
    auto calc3=[&](const int&x,int lim)
    {
        if(x>=0)return 1ll*(x>=lim);
        if(-x>=lim)return -x-lim+1;
        //v>=(j-k)
        //v-(j-k)+1
        //v-j+k+1
        return 0ll;
    };
    for(int i=1;i<=n+1;i++)
    {
        //j<=k 
        int p=calc1(b[i])*calc1(c[i])%mod*calc1(e[i])%mod,v=abs(d[i]);
        int p1=calc2(b[i])*calc1(c[i])%mod*calc1(e[i])%mod;
        int q=calc1(b[i])*calc1(c[i])%mod*calc1(d[i])%mod;
        int q1=calc1(b[i])*calc2(c[i])%mod*calc1(d[i])%mod;
        int r1=0,r2=0,r3=0,r4=0,r5=0;
        for(int j=0;j<=abs(a[i]);j++)
        {
            (r1+=f[i-1][j])%=mod;
            (r2+=f[i-1][j]*j)%=mod;
            (r3+=g[i-1][j])%=mod;
            (r4+=g[i-1][j]*j)%=mod;
            (r5+=f[i-1][j]*j*j)%=mod;
            if(j-v-1>=0)
            {
                r1=(r1-f[i-1][j-v-1]+mod)%mod;
                r2=(r2-f[i-1][j-v-1]*(j-v-1)%mod+mod)%mod;
                r3=(r3-g[i-1][j-v-1]+mod)%mod;
                r4=(r4-g[i-1][j-v-1]*(j-v-1)%mod+mod)%mod;
                r5=(r5-f[i-1][j-v-1]*(j-v-1)*(j-v-1)%mod+mod)%mod;
            }
            if(a[i]==j||-a[i]>=j)
            {
                if(d[i]>=0)
                {
                    (f[i][j]+=r1*p)%=mod;
                    (g[i][j]+=r3*p)%=mod;
                    (g[i][j]+=(r1*j-r2+mod)*p1)%=mod;
                }
                else
                {
                    (f[i][j]+=(r1*(v-j+1+mod)%mod+r2)*p)%=mod;
                    (g[i][j]+=(r3*(v-j+1)%mod+r4)*p)%=mod;
                    (g[i][j]+=(mod-r5+mod-(v-2*j+1)*r2%mod+j*(v-j+1)%mod*r1%mod)*p1)%=mod;
                }
            }
        }
        v=abs(e[i]);r1=r2=r3=r4=r5=0;
        for(int j=abs(a[i-1]);j>=0;j--)
        {
            if(j+v+1<=abs(a[i-1]))
            {
                r1=(r1-f[i-1][j+v+1]+mod)%mod;
                r2=(r2-f[i-1][j+v+1]*(j+v+1)%mod+mod)%mod;
                r3=(r3-g[i-1][j+v+1]+mod)%mod;
                r4=(r4-g[i-1][j+v+1]*(j+v+1)%mod+mod)%mod;
                r5=(r5-f[i-1][j+v+1]*(j+v+1)*(j+v+1)%mod+mod)%mod;
            }
            if(a[i]==j||-a[i]>=j)
            {
                if(e[i]>=0)
                {
                    (f[i][j]+=r1*q)%=mod;
                    (g[i][j]+=r3*q)%=mod;
                    (g[i][j]+=(r2-j*r1%mod+mod)*q1)%=mod;
                }
                else 
                {
                    (f[i][j]+=(r1*(v+j+1)%mod-r2+mod)*q)%=mod;
                    (g[i][j]+=(r3*(v+j+1)%mod-r4+mod)*q)%=mod;
                    //(v-j+k+1)(j-k)
                    //-j^2+j(v+2k+1)-k(v+k+1)
                    (g[i][j]+=(mod-r5+(v+2*j+1)*r2%mod+mod-j*(v+j+1)%mod*r1%mod)*q1)%=mod;
                }
            }
            (r1+=f[i-1][j])%=mod;
            (r2+=f[i-1][j]*j)%=mod;
            (r3+=g[i-1][j])%=mod;
            (r4+=g[i-1][j]*j)%=mod;
            (r5+=f[i-1][j]*j*j)%=mod;
        }
/*
        for(int j=max(a[i-1],0ll);j<=abs(a[i-1]);j++)if(f[i-1][j])
            for(int k=max(a[i],0ll);k<=abs(a[i]);k++)
            {
                if(j<=k)//a[i]-a[i-1] ->b[i]
                {
                    int cnt=calc1(c[i])*calc3(d[i],k-j)%mod*calc1(e[i])%mod;
                    // (f[i][k]+=f[i-1][j]*calc1(b[i])%mod*cnt)%=mod;
                    //(v-k+j+1)*(k-j)
                    //-j^2-j(v-k+1)+jk+k(v-k+1)
                    //-j^2-j(v-2k+1)+k(v-k+1)
                    // (g[i][k]+=g[i-1][j]*calc1(b[i])%mod*cnt+f[i-1][j]*calc2(b[i])*(k-j)%mod*cnt)%=mod;
                }
                else //a[i-1]-a[i] ->c[i]
                {
                    int cnt=calc1(b[i])*calc1(d[i])%mod*calc3(e[i],j-k)%mod;
                    // (f[i][k]+=f[i-1][j]*calc1(c[i])%mod*cnt)%=mod;
                    //  (g[i][k]+=g[i-1][j]*calc1(c[i])%mod*cnt+f[i-1][j]*calc2(c[i])*(j-k)%mod*cnt)%=mod;
                }
            }
*/
    }
    int tot=1;
    for(int i=1;i<=n+1;i++)tot=tot*calc1(a[i])%mod*calc1(b[i])%mod*calc1(c[i])%mod*calc1(d[i])%mod*calc1(e[i])%mod;
    int a1=f[n+1][0],a2=g[n+1][0];
    cout<<a2<<' '<<(tot-a1+mod)%mod<<endl;
    return 0;
}
/*
2
1 1
1 2
2 1
-1 -1
-1 -1

3
-1 -2 2
1  3  0
-3 0 -2
1 -3  0
1 3   3
*/