T1 破碎的矩阵

部分分设置

：暴力枚举，直接检验。

：暗示正解。

题目思路

考虑在时，对于每个格子可以填。那么所有的格子对应的数都只有一个二进制位。当所有行异或和的异或和等于所有列异或和的异或和时，在前行列的格子随意的填数，第行和第列总有唯一合法的填数方案。
考虑在时，对于每个格子对应的数有个二进制位，且不受限制，此时相比于，个二进制位相互独立，所以在前行列的格子随意的填数，第行和第列也总有唯一合法的填数方案。
考虑当所有行异或和的异或和不等于所有列异或和的异或和时，矩阵填数一定不合法，此时答案为。否则，矩阵内前行列可以随意填数，每个位置有种填数方案，此时答案为。
时间复杂度。

考察知识点

位运算，快速幂。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+6;

int t,n,m,p,d;

long long x,a[N],b[N],suma,sumb,ans;

long long qpow(long long u,int v){
    long long rep=1;
    while(v>0){
        if(v&1){
            rep=(rep*u)%p;
        }
        u=(u*u)%p;
        v>>=1;
    }
    return rep;
}

int main(){
    scanf("%d",&t);
    while(t--){
        suma=0;sumb=0;
        scanf("%d%d%lld%d",&n,&m,&x,&p);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            suma^=a[i];
        }
        for(int i=1;i<=m;i++){
            scanf("%lld",&b[i]);
            sumb^=b[i];
        }
        if(suma!=sumb){
            printf("0\n");
            continue;
        }
        ++x;
        x%=p;
        ans=qpow(x,n-1);
        ans=qpow(ans,m-1);
        printf("%lld\n",ans);
    }
    return 0;
}

T2 点与面

部分分设置

纯暴力

提示正解

解题思路

对于前30%数据，我们可以暴力枚举五元组，在时间内解决这个问题。
我们考虑枚举W型最中间的点，既，我们考虑的左边，要找一个比，还要找一个，那么实际上，对于左侧，低于的点，对答案的贡献为左侧比大的点，我们这一步可以用BIT维护,得到左右两边的贡献之后，使用乘法原理将他们组合，就能计算出答案。
统计时，直接枚举是单次的，总复杂度可以得到40%的分数，考虑我们刚才维护的信息，和这个类似，我们也可以用类似的方式，再维护一颗BIT来完成统计。 得到左右两边的贡献之后，使用乘法原理将他们组合，就能计算出答案。
总时间复杂度可以做到，拿到全部分数。

考察知识点

BIT(树状数组)，乘法原理

代码实现

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
const int p = 998244353;
int inc(int a,int b) {
    a+=b;
    return a>=p?a-p:a;
}
int dec(int a,int b) {
    a-=b;
    return a<0?a+p:a;
}
int mul(int a,int b) {
    return 1LL*a*b%p;
}
int a[5000100],b[5000100],h[5000100],sum1[5001000],sum2[5001000];
int n,ans=0,m=0;
int lowbit(int k)
{
    return k&(-k);
}
void add_a(int k)
{
    while(k<=m)
    {
        a[k]=inc(a[k],1);
        k+=lowbit(k);
    }
}
void add_b(int k,int sum)
{
    while(k<=m)
    {
        b[k]=inc(b[k],sum);
        k+=lowbit(k);
    }
}
int ask_a(int k)
{
    int res=0;
    while(k)
    {
        res=inc(res,a[k]);
        k-=lowbit(k);
    }
    return res;
}
int ask_b(int k)
{
    int res=0;
    while(k)
    {
        res=inc(res,b[k]);
        k-=lowbit(k);
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;m=max(m,h[i]),i++)
        scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
    {
        add_a(h[i]);
        add_b(h[i],dec(ask_a(m),ask_a(h[i])));
        sum1[i]=ask_b(h[i]-1);
    }
    memset(a,false,sizeof(a));
    memset(b,false,sizeof(b));
    for(int i=n;i>=1;i--)
    {
        add_a(h[i]);
        add_b(h[i],dec(ask_a(m),ask_a(h[i])));
        sum2[i]=ask_b(h[i]-1);
    }
    for(int i=1;i<=n;i++)
        ans=inc(ans,mul(sum1[i],sum2[i]));
    printf("%d\n",ans);
}

T3 信息传递

部分分设置

：暴力。

：留给有需要的复杂度选手。

题目思路

首先，位置是环形的，可以考虑断环为链（长度倍），那么所有人都知道Venn被飞的消息等价于传播的左端点到右端点长度。
考虑从每个位置开始，第秒后最远可以将Venn被飞的消息传播到的最左位置和最右位置。设答案为，则时，，时，。由于，所以每经过，边界位置总会扩大，考虑倍增。对于断环为链后的每个位置，维护从当前位置开始传播秒后的边界位置和最右位置，则有转移
，区间最大/最小值用线段树/ST表维护，然后对于个询问，倍增求出答案即可。
时间复杂度 。

考察知识点

倍增，线段树/ST表。

代码实现

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

const int maxn=1e5;
int n, l[17][17][maxn], r[17][17][maxn];

pair<int, int> qry(int i, int l2, int r2) {
    int b=31-__builtin_clz(r2-l2+1);
    return {max(l[i][b][l2], l[i][b][(r2-(1<<b)+1)%n]-(r2-(1<<b)+1-l2)), max(r[i][b][(r2-(1<<b)+1)%n], r[i][b][l2]-(r2-(1<<b)+1-l2))};
}

int main() {
    scanf("%d",&n);
    if(n==1) {
        puts("0");
        return 0;
    }
    for(int i=0; i<n; ++i)
        scanf("%d",&l[0][0][i]);
    for(int i=0;i<n;++i)
        scanf("%d",&r[0][0][i]);
    for(int i=1; i<17; ++i) {
        int a=1<<(i-1);
        for(int j=0; j<n; ++j) {
            l[0][i][j]=max(l[0][i-1][j], l[0][i-1][(j+a)%n]-a);
            r[0][i][j]=max(r[0][i-1][(j+a)%n], r[0][i-1][j]-a);
        }
    }
    for(int i=1; i<17; ++i) {
        for(int j=0; j<17; ++j) {
            int a=1<<j;
            for(int k=0; k<n; ++k) {
                int l2=k-l[i-1][j][k], r2=k+a-1+r[i-1][j][k];
                if(r2-l2>=n-1) {
                    l[i][j][k]=r[i][j][k]=n;
                    continue;
                }
                if(l2<0) {
                    l2+=n;
                    r2+=n;
                }
                tie(l[i][j][k], r[i][j][k])=qry(i-1, l2, r2);
                l[i][j][k]+=l[i-1][j][k];
                r[i][j][k]+=r[i-1][j][k];
            }
        }
    }
    for(int i=0; i<n; ++i) {
        int l2=i,r2=i,ans=1,l3,r3;
        for(int j=16; j>=0; --j) {
            tie(l3, r3)=qry(j, l2, r2);
            l3=l2-l3;
            r3+=r2;
            if(r3-l3<n-1) {
                ans+=1<<j;
                l2=l3;
                r2=r3;
                if(l2<0) {
                    l2+=n;
                    r2+=n;
                }
            }
        }
        printf("%d ",ans);
    }
    return 0;
}