Day -14

在路上偶遇了信竞老师。在他的建议下，我每天晚自习去集训。

Day -12

不用写作业真爽。

Day -5

这一周的所有集训我都是先做出T2再做出T1的，这使我有不祥的预感。

Day 0

所有与具体做法强相关的将放在题解部分。

T1（上）

对着草稿纸比划了 0.5h，最后拉马努金附体，靠感觉猜了个贪心，证不出来。

小样例过了，程序在大样例的答案居然比样例输出还大，这使我惊慌且疑惑，调了 0.5h 没调出来。

T2

正难则反。反着想不久 ≤0.5h 就想出来了。T2 比 T1 简单，Day -5 的预感成真了。

踩了俩坑。

• 没特判 $c_{i}=c_{i+1}, d_{i}= d_{i+1}$，最后加了个 unique 去重。
• 写少了俩取模。这个通过 typedef __int128 ll; 发现输出有变化，于是查出来了。

然后第 2, 3 个大样例一起过了。

T3

太长没看。

T4

想出了 ST 表 $\Theta(n\log^2n+q[(L-k)+\log n])$ 的做法（其中 $L=r-l+1$），然而写挂了，只有小样例过得去。

在调 T4 和 T1 之间还是选择了 T1，因为就算这种解法调好也不超过 40 pts，事实证明这是明智的。

T1（下）

此时距离结束还有 2h.

首先重构了一下代码。原来的代码是将 $s_1$ 与 $s_2$ 均未被分割的编成一块，统一计算转移，重构之后就是一个一个字符转移的，虽然常数稍大但是更简洁清晰。

然后就是打了几个断点，手造样例。中途一个插曲是造样例的时候把顺序造成 $s_1, t_1, s_2, t_2$ 了，还以为自己发现了症结所在。

最后终于发现自己把 n1 = (t1[i]=='0' || t1[i]!=t1[i-1]) 打成了 n1 = (t1[i]==0 || t1[i]!=t1[i-1])，打少了个单引号，这导致了没有把连续的 $0$ 隔开。

改完之后就过了全部样例，此时距离结束还有 45min.

然后我心情舒坦地上了个厕所。（吸取 CSP 教训，我这次上了 3 次厕所）

等

例行拜了拜电子佛祖。

后

老师请吃了披萨，好耶！

同学们太热情了，刚出炉的披萨立刻被瓜分了，只能等他们吃饱了才能吃到。

肴核既尽，杯盘狼藉。老师先走了，同学们在打牌。我不会打牌，于是也走了。

分

T1 也许是因为贪心难以证明导致洛谷迟迟没出数据。

自测民间数据 T1, T2 AC.

T4 估计寄了，$\le 10\text{ pts}$.

一首改编的打油诗

一题夸自己，两题了不起。 T4 写挂了？有写就是牛。

希望能时刻保持良好的心态。

Day +6

出分了，$100+100+0+0=200$。

据说 T3 输出 $1$ 能骗分。痛失分数。

题解

T1 题解

不难发现原题可以转化为： 将 $s_1, s_2$ 分别划成几个区间，区间内打乱。

例如样例
$s_1=\texttt{011101}$
$t_1=\texttt{111010}$
可以划成 $011/1/0/1$.

也就是说，我们在每个 $t_i=0$ 的左右分别划一刀。

接下来就是贪心。

如果 $i$ 所在的段内同时有未匹配的 $s_{1,j}=s_{2,k}$，就把 $s_{1,j}, s_{2,k}$ 挪到 $i$ 的位置并标记为匹配。

考场上粗略地证了一下，但是考完发现有漏洞。

如果一个猜想你证不出来，但是靠它过了所有大样例，那么它就是对的。proof: 我们用 C++ 验证了这个猜想。

Code

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

const int maxn=1e5+100;

char s1[maxn], s2[maxn], t1[maxn], t2[maxn];

struct area {
    int cnt[4];
} sa1[maxn], sa2[maxn];
int belong1[maxn], belong2[maxn];
int sa1tot, sa2tot;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("edit.in", "r", stdin);
    freopen("edit.out", "w", stdout);
    
    int t;
    cin >> t;
    
    while (t--){
        memset(sa1, 0, sizeof sa1);
        memset(sa2, 0, sizeof sa2);
        sa1tot = sa2tot = 0;
        
        int n;
        cin >> n;
        cin >> s1+1 >> s2+1 >> t1+1 >> t2+1;
        
        for (int i=1; i<=n; i++){
            int n1 = (t1[i]=='0' || t1[i]!=t1[i-1]),
                n2 = (t2[i]=='0' || t2[i]!=t2[i-1]);
                
            sa1tot += n1;
            sa2tot += n2;
            
            sa1[sa1tot].cnt[s1[i]-'0']++;
            sa2[sa2tot].cnt[s2[i]-'0']++;
            
            belong1[i] = sa1tot;
            belong2[i] = sa2tot;
        }
        
        int ans=0;
        for (int i=1; i<=n; i++){
            int bl1=belong1[i], bl2=belong2[i];
            if (sa1[bl1].cnt[0] && sa2[bl2].cnt[0]){
                sa1[bl1].cnt[0]--;
                sa2[bl2].cnt[0]--;
                ans++;
            } else if (sa1[bl1].cnt[1] && sa2[bl2].cnt[1]) {
                sa1[bl1].cnt[1]--;
                sa2[bl2].cnt[1]--;
                ans++;
            }
        }
        
        cout << ans << '\n';
    }
    
    
    return 0;
}

T2 题解

基本操作：先将限制条件按 $c_i$ 排序。

不难发现，如果一个位置没有被两个限制夹着，那么 $a_i, b_i$ 可以任取，即每个位置有 $v^2$ 种取值。
证明也很简单，如果一个位置的左边没有限制而右边有，那我们只需令 $x_i\ne a_i$，
如果右边没有限制而左边有，那么填什么都不影响。

那如果被两个限制 $c_j, c_{j+1}$ 夹着呢？
正难则反。
我们考虑 $a_i, b_i$ 应该等于什么才能让 $x_{c_{j+1}} \mathop{\ne}\limits^{\text{一定}} d_{j+1}$.
那么显然 $a_i, b_i$ 一定是一条完整的逻辑链条，才能把 $x_{c_{j+1}}$ 限制死。
链条的起始端一定为 $d_i$，中间是任意的（有 $v$ 种取值），末端一定不为 $d_{i+1}$（有 $(v-1)$ 种取值）

于是 $negans=v^{\Delta c}(v-1)$，其中 $\Delta c=c_{j+1}-c_j$.

该段的答案为 $v^{2\Delta c}-negans$.

把所有段（包括没有被两个限制夹着的段）的答案乘起来即可。

Code

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

typedef long long ll;

const ll maxm=1e5+100, mod=1e9+7;

struct xianz {
    long long c, d;
    bool operator < (xianz &other){
        return c < other.c;
    }
    bool operator == (xianz &other){
        return c==other.c && d==other.d;
    }
} xz[maxm]; 

ll qpow(ll a, ll b){
    ll ans=1;
    while (b){
        if (b&1){
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("assign.in", "r", stdin);
    freopen("assign.out", "w", stdout);
    
    int t;
    cin >> t;
    
    while (t--){
        ll n, m, v;
        cin >> n >> m >> v;
        for (int i=1; i<=m; i++){
            cin >> xz[i].c >> xz[i].d;
        }
        
        sort(xz+1, xz+m+1);
        m = unique(xz+1, xz+m+1) - (xz+1);
        
        bool ansis0=false;
        ll ans=1;
        for (int i=2; i<=m; i++){
            if (xz[i].c == xz[i-1].c){
                ansis0 = true;
                break;
            }
            ll posans = qpow(v, 2*(xz[i].c-xz[i-1].c)),
               negans = qpow(v, xz[i].c-xz[i-1].c-1);
            negans *= v-1;
            negans %= mod;
            ans *= (posans-negans + mod) % mod;
            ans %= mod;
        }
        
        if (m){
            ans *= qpow(v, 2*(xz[1].c-1));
            ans %= mod;
            ans *= qpow(v, 2*(n-xz[m].c));
            ans %= mod;
        } else {
            ans *= qpow(v, 2*(n-1));
            ans %= mod;
        }
        
        
        if (ansis0){
            cout << "0\n";
        } else {
            cout << ans%mod << '\n';
        }
    }
    
    
    return 0;
}