CF1027E Inverse Coloring

题意

给定 矩形，求黑白染色数量满足任意 子矩阵黑格数量为 ，且任意同色连通块大小小于 。

？

！

基本思路

首先有几点做题的基础：

  1. 我写的题意与原题意是一致的，证明考虑归纳法导出矛盾（ 会差 ，这个可以忽略）。

  2. 第一行与第一列确定后，整个矩形就已经确定。在转化的题意下证明可以参考 2021 省选 矩阵游戏。

  3. 各个同色连通块必然是矩形，并且对应于第一行的某个同色段与第一列的某个同色段。

这样，题意最终被转化为，划分两个序列，使得它们最长同色段之积小于等于 。

首先，两个序列的第一位的颜色必须相同，所以最后除以二。

子问题 1

先解决最长同色段小于等于 的子问题，设为 。

  1. 设 表示前 个点最后一段长为 ，复杂度 （结合以下 2.1 对应大部分原题 做法）。

  2. 对 1.1 进行前缀和优化，复杂度 （结合以下 2.1 对应大部分原题 做法）。

  3. 发现 1.1 是一个 次递推式，使用矩阵快速幂，复杂度 。

  4. 常系数齐次线性递推，复杂度 。

  5. 容斥，设当前在求 ，枚举不合法的段数 ，在 中放置 个长度为 的段，然后剩下的任选。

    但是你发现对于第一位，情况特殊一点，因为如果你后面 位已经是不合法的了，那么 第一位在第一段且第一段不合法/第一位不在第一段且第一段不合法 就会重复（这两个的区别在于第一位反色一次，但是你本身要整体选择一次颜色），此时你钦定第一位是否在一段内就可以解决这个问题（当然你也可以再容斥一次）。

    注意两个组合数代替了整体乘二。复杂度 。

子问题 2

现在我们能快速求出 了，考虑如何得到答案：

  1. 直接枚举其中一个序列的最长连续段，其贡献使用差分求出。然后另一个的长度上限就确定了，并且贡献恰好是前缀和（结合 1.5 为 的做法）。

  2. 你发现这里有一个整除的形式，所以可以整除分块。对于 另一个的长度 进行整除分块，然后之前枚举的贡献现在是一个区间，由于能求出来的就是前缀和，于是求两个值做差即可。

    结合 1.5 复杂度还是 的，但是常数极小， 只用不到 5s。

    结合 1.3 和 1.5 的理论复杂度为 ；

    结合 1.4 和 1.5 的理论复杂度为 ，不过常数极大，除非你的板子非常优秀不然大概率跟矩阵快速幂差不多。

    当然，如果模数是 的话那么可以卢卡斯定理把 开得巨大应该能区分出常系数齐次线性递推。

CODE

当然，在本题的数据范围中数据分治加了没用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=10000010,K=61,FSIZE=1<<10,mo=998244353;
int n,k,ans,g[N],pw2[N],fac[N],inv[N];
struct matrix{
    int n=0,a[K][K];
    matrix(int _,int o=2){
        n=_;memset(a,0,sizeof(a));
        if(o==2){
            for(int i=0;i<n;++i) a[0][i]=1;
            for(int i=1;i<n;++i) a[i][i-1]=1;
        }else if(o==1) for(int i=0;i<n;++i) a[i][i]=1;
    }
    matrix operator*(const matrix &b){
        matrix re(n,0);
        for(int k=0;k<n;++k)
        for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            re.a[i][j]=(re.a[i][j]+(ll)a[i][k]*b.a[k][j])%mo;
        return(re);
    };
};
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
ll power(ll base,int m){
    ll re=1;
    for(;m;m>>=1,base=base*base%mo)
        if(m&1) re=re*base%mo;
    return(re);
}
ll power(matrix base,int m){
    matrix re(base.n,1);
    for(;m;m>>=1,base=base*base)
        if(m&1) re=re*base;
    return(re.a[0][0]);
}
ll C(int n,int m){
    return((ll)fac[n]*inv[m]%mo*inv[n-m]%mo);
}
ll solve(int i){
    if(i>n) i=n;
    if(!i) return(0);
    if(g[i]) return(g[i]);
    // if(i<=10) return(g[i]=power(matrix(i),n)*2%mo);
    int re=pw2[n];
    for(int j=1;j*(i+1)<=n;++j)
        re=(re+(j&1?-1:1)*(C(n-j*i,j)+C(n-j*i-1,j-1))*pw2[n-j*(i+1)])%mo;
    if(re<0) re+=mo;
    return(g[i]=re);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(k);--k;
    for(int i=pw2[0]=inv[0]=fac[0]=1;i<=n;++i){
        if((pw2[i]=pw2[i-1]<<1)>=mo) pw2[i]-=mo;
        inv[i]=power(fac[i]=(ll)fac[i-1]*i%mo,mo-2);
    }
    for(int l=1,r;l<=k;l=r+1){
        r=k/(k/l);
        ans=(ans+(solve(r)-solve(l-1)+mo)*solve(k/l))%mo;
    }
    printf("%lld\n",(ans*ll(mo+1)/2)%mo);
    return(0);
}
≡