模拟赛题1 solution

想必大家看这篇题解的时候已经了吧。

1、小肥柴

Subtask #1

额，只要会就行了……

Subtask #2

高精顺利解决（有人会这么干么……

Subtask #3

为质数，此时一定存在在模意义下的逆元，用快速幂就行。

Question #1

为什么不是质数时不行？

因为此时不一定存在在模意义下的逆元。

考虑逆元的意义。

此时，由定理得，和有解当且仅当，因此必须互质，因此需要是质数。

Subtask #4

考虑质因数分解

个数的相当于是这个数的所有质因子的幂次取，再乘起来。

但是这样的复杂度是。除非你的常数小于2，不然肯定过不了。现实是：场上这么做的人都被最后两个点卡了。

Subtask #5

考虑如何优化质因数分解。

主要有三种方法：

线性筛预处理最小质因子，复杂度

预处理的所有质数，然后直接分解，复杂度

Pollard Rho，期望复杂度。

附上代码（用的是预处理根号以内的所有质数）

#include<bits/stdc++.h>
using namespace std;
int n,p;
int prime[5005],cnt;
bool vis[5005];
void get_prime(int n) {
    for (int i = 2; i <= n; ++i)
        if (!vis[i]) {
            prime[++cnt] = i;
            for (int j = i * 2; j <= n; j += i)
                vis[j] = 1;
        }
}
int has[10000005];
int main() {
    scanf("%d%d", &n, &p);
    get_prime(5000);
    for (int x, i = 1; i <= n; ++i) {
        scanf("%d", &x);
        for (int j = 1; j <= cnt; ++j)
            if (!(x % prime[j])) {
                int t = 1;
                while (!(x % prime[j]))
                    x /= prime[j], t = t * prime[j];
                if (has[prime[j]] < t)
                    has[prime[j]] = t;
            }
        if (x > 1)
            has[x] = x;
    }
    int ans = 1;
    for (int i = 1; i <= 10000000; ++i)
        if (has[i])
            ans = 1ll * ans * has[i] % p;
    printf("%d\n", ans);
}

2、蜜桃猫

Subtask #1

暴力枚举每个字符串的正反状态。貌似能拿的分挺多的？🤔

Subtask #2

可以处理一下两两串之间的关系。

两个串，设翻转后为，表示两串相同的位数。

若，则两串可以正反状态相同。

若，则两串可以状态不同。

那么两两之间一共有四种状态：

无论怎样都不行（直接输出0）

状态必须相同

状态必须相反

状态怎样都行

那么我们可以用二分图来表示。对应的四种状态：

直接跳出，输出零

在两两之间连一条边权为0的边

在两两之间连一条边权为1的边

不管，直接跳过。

这样，原问题就转化为了二分图染色问题，深搜就行了。

时间复杂度：。常数略大就会。

Subtask #3

发现时间复杂度瓶颈在处理两两之间状态上，可以考虑用来优化01串计数。

时间复杂度：

由于，完全可以看作是常数，因此复杂度没问题。

附上代码。

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int T,n,m,k;
char s[2005][105];
bitset<105> a[2005],b[2005];
vector< pair<int,int> > g[2005];
int mi2[2005];
int col[2005];
int dfs(int u,int c) {
    col[u] = c;
    for (auto p:g[u]) {
        int v = p.first, w = p.second;
        if (col[v]) {
            if (w == 0 && col[u] != col[v])
                return -1;
            if (w == 1 && col[u] == col[v])
                return -1;
        } else {
            int f = dfs(v, (w == 0) ? c : 3 - c);
            if (f == -1)
                return -1;
        }
    }
    return 1;
}
int main() {
    mi2[0] = 1;
    for (int i = 1; i <= 2000; ++i)
        mi2[i] = 1ll * mi2[i - 1] * 2 % mod;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; ++i)
            scanf("%s", s[i] + 1), a[i].reset(), b[i].reset(), g[i].clear();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (s[i][j] == '1')
                    a[i][j] = 1, b[i][m - j + 1] = 1;
        bool yes = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j) {
                int t1 = (a[i] & a[j]).count(), t2 = (a[i] & b[j]).count();
                //cerr<<i<<" "<<j<<" "<<t1<<" "<<t2<<endl;
                if (t1 >= k && t2 >= k)
                    continue;
                else if (t1 >= k) {
                    g[i].push_back(make_pair(j, 0));
                    g[j].push_back(make_pair(i, 0));
                } else if (t2 >= k) {
                    g[i].push_back(make_pair(j, 1));
                    g[j].push_back(make_pair(i, 1));
                } else {
                    yes = 0;
                }
            }
        if (!yes) {
            puts("0");
            continue;
        } else {
            int ans = 0;
            memset(col, 0, sizeof(col));
            for (int i = 1; i <= n; ++i)
                if (!col[i]) {
                    if (dfs(i, 1) == -1)
                        yes = 0;
                    ans++;
                }
            if (!yes)puts("0");
            else printf("%d\n", mi2[ans]);
        }
    }
}

3、哈啦鱼

Subtask #1

瞎暴力就行了

Subtask #2

找规律

Subtask #3

还是找规律

50分大礼包？（窃喜

Subtask #4

首先，由于原图是一棵树，因此它的连通子图也是一棵树，因此边数一定是点数减一。

然后需要将边定向，这里采用从编号大的点向编号小的点连边。

设定向后点的入度是。

那么，如果区间满足要求，则一定有：。

我们可以考虑枚举右端点，在数列上从左往右扫一遍，扫的同时将相关的所有边定向，并将所有出边计入入度。设为以为终点的的后缀和。那么，如果，则当前区间满足要求。还有一点，在处理出边时会修改数组的值，因此还需要在上区间修改。

我们考虑维护，这样，由于此时，因此原问题就变成了要求维护一个支持区间加，区间最值及其出现次数，可以用线段树解决。

附上代码：

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

typedef pair<int, int> pii;

const int maxn = 1200005;
struct node
{
    int val, sum, tag;
    int l, r, ls, rs;
    void clear(int x, int y)
    {
        l = x; r = y; tag = ls = rs = val = sum = 0;
    }
    bool match(int x, int y)
    {
        return l == x && y == r;
    }
}tr[maxn << 1];
int T, n, k;
vector<int> g[maxn];

void update(int u)
{
    int ls = tr[u].ls, rs = tr[u].rs;
    if(ls + rs == 0)
        return;
    tr[u].val = max(tr[ls].val, tr[rs].val);
    tr[u].sum = 0;
    if(tr[u].val == tr[ls].val)
        tr[u].sum += tr[ls].sum;
    if(tr[u].val == tr[rs].val)
        tr[u].sum += tr[rs].sum;
}

void downdate(int u)
{
    int ls = tr[u].ls, rs = tr[u].rs;
    int tag = tr[u].tag; tr[u].tag = 0;
    if(ls + rs == 0)
        return;
    tr[ls].val += tag; tr[ls].tag += tag;
    tr[rs].val += tag; tr[rs].tag += tag;
}

void mt(int x, int y)
{
    tr[k].clear(x, y);
    if(x == y)
    {
        tr[k].val = x;
        tr[k].sum = 1;
        return;
    }
    int mid = (x + y) >> 1, t = k;
    k ++; tr[t].ls = k; mt(x, mid);
    k ++; tr[t].rs = k; mt(mid + 1, y);
    update(t);
}

void add(int o, int x, int y, int v)
{
    if(tr[o].match(x, y))
    {
        tr[o].tag += v;
        tr[o].val += v;
        return;
    }
    downdate(o);
    int mid = (tr[o].l + tr[o].r) >> 1;
    if(x <= mid)
        add(tr[o].ls, x, min(y, mid), v);
    if(y > mid)
        add(tr[o].rs, max(mid + 1, x), y, v);
    update(o);
}

pii query(int o, int x, int y)
{
    if(tr[o].match(x, y))
        return make_pair(tr[o].val, tr[o].sum);
    downdate(o);
    int mid = (tr[o].l + tr[o].r) >> 1;
    pii s1 = make_pair(0, 0), s2 = make_pair(0, 0), ret = make_pair(0, 0);
    if(x <= mid)
        s1 = query(tr[o].ls, x, min(y, mid));
    if(y > mid)
        s2 = query(tr[o].rs, max(mid + 1, x), y);
    ret.first = max(s1.first, s2.first);
    if(ret.first == s1.first)
        ret.second += s1.second;
    if(ret.first == s2.first)
        ret.second += s2.second;
    update(o);
    return ret;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        g[i].clear();
    for(int i = 1; i < n; ++ i)
    {
        int x, y;
		scanf("%d%d", &x, &y);
        if(x > y)
            swap(x, y);
        g[y].push_back(x);
    }
    k = 1; mt(1, n);
    long long ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        for(int p : g[i])
            add(1, 1, p, 1);
        pii now = query(1, 1, i);
        //printf("%d %d\n", now.first, now.second);
        if(now.first == i)
            ans += now.second;
    }
    printf("%lld\n", ans);
    return 0;
}

4、简单题

Subtask #1

瞎搞搞就行了，真•送分

Subtask #2

暴力

Subtask #3

设计一个。设表示第次使用魔法卷轴，物理攻击为，魔法攻击为的概率，然后暴力转移，时间复杂度为。

发现是独立的两维，可以分开来处理，这样优化，时间复杂度为。

转移式子如下（下面讨论其中一种情况）：

定义为第次使用魔法卷轴，物理攻击为的概率。设，再设为的逆元，则有

Subtask #4

矩阵快速幂的题目一般会一个量特别大，一个量特别小。 —— 关怀巨佬

正如巨佬所说的，本题中特别小，特别大。

重新看一下上面的转移式子，仅与有关，与的参数一致，因此我们可以考虑一下矩阵优化。

考虑将用矩阵的形式表达，然后直接用初始矩阵乘上矩阵的幂次方次就行了。时间复杂度，主要优化了。

附上这个subtask的代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int fastpow(int a,int p)
{
	int ans=1;
	while(p)
	{
		if(p&1)
		    ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;p>>=1;
	}
	return ans;
}
int inv(int x)
{
    return fastpow(x,mod-2);
}
int n,x,y,t,q;
struct Matrix
{
	int m[11][11];
	void clear()
	{
		memset(m,0,sizeof(m));
	}
	void init()
	{
		clear();
		for(int i=1;i<=n;++i)
		    m[i][i]=1;
	}
}bas;
Matrix operator * (Matrix A,Matrix B) {
    Matrix C;
    C.clear();
    for (int i = 1; i <= n; ++i)
        for (int k = 1; k <= n; ++k)
            if (A.m[i][k])
                for (int j = 1; j <= n; ++j)
                    C.m[i][j] = (C.m[i][j] + 1ll * A.m[i][k] * B.m[k][j] % mod) % mod;
    return C;
}
Matrix fastpow(Matrix a,ll p)
{
	Matrix ans;
	ans.init();
	while(p)
	{
		if(p&1)
		    ans=ans*a;
		a=a*a;
		p>>=1;
	}
	return ans;
}
int solve(int s,ll k,int t)
{
	Matrix A=fastpow(bas,k);
	Matrix B;
	B.clear();
	B.m[s][1]=1;
	B=A*B;
	return B.m[t][1];
}
int main()
{
	scanf("%d%d%d%d%d",&n,&x,&y,&t,&q);
	bas.clear();
	for(int i=1;i<=n;++i)
	{
		int L=max(1,i-t),R=min(n,i+t);
		int p=inv(R-L+1);
		for(int j=L;j<=R;++j)
		    bas.m[i][j]=p;
	}
	while(q--)
	{
		ll k;int u,v;
		scanf("%lld%d%d",&k,&u,&v);
		int ans1=solve(x,k,u),ans2=solve(y,k,v);
		int ans=1ll*ans1*ans2%mod;
		printf("%d\n",ans);
	}
}

Subtask #5

可是这样还是不行，太大了，乘上就直接炸了。

考虑预处理矩阵的幂次,把幂次k拆分成 (按根号分开)，然后预处理矩阵的和次幂。

时间复杂度为。如果过于大，还是过不去。

还可以再拆成三部分，时间复杂度为。可是如果过大，还是过不去，并不能解决问题。

Subtask #6

但其实我们可以发现拆成三份后每次询问实际上是三个矩阵乘上一个列向量，那么可以将列向量一次与三个矩阵相乘，结果始终是列向量形式的。这样，时间复杂度就是。这样，过大的问题就解决了。

最后附上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int fastpow(int a,int p)
{
	int ans=1;
	while(p)
	{
		if(p&1)
		    ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;p>>=1;
	}
	return ans;
}
int inv(int x){return fastpow(x,mod-2);}
int n,x,y,t,q;
struct Matrix
{
	int m[11][11];
	void clear()
	{
		memset(m,0,sizeof(m));
	}
	void init()
	{
		clear();
		for(int i=1;i<=n;++i)m[i][i]=1;
	}
}A[100005],B[100005],C[100005],bas;
Matrix operator * (Matrix A,Matrix B) {
    Matrix C;
    C.clear();
    for (int i = 1; i <= n; ++i)
        for (int k = 1; k <= n; ++k)
            if (A.m[i][k])
                for (int j = 1; j <= n; ++j)

                    C.m[i][j] = (C.m[i][j] + 1ll * A.m[i][k] * B.m[k][j] % mod) % mod;
    return C;
}
int Ans[11],tmp[11];
int solve(int p,int X,int Y,int Z,int u)
{
	memset(Ans,0,sizeof(Ans));
	memset(tmp,0,sizeof(tmp));
	tmp[p]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		    Ans[i]=(Ans[i]+1ll*A[X].m[i][j]*tmp[j]%mod)%mod;
	for(int i=1;i<=n;++i)
	    tmp[i]=Ans[i];
	for(int i=1;i<=n;++i)
	    Ans[i]=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		    Ans[i]=(Ans[i]+1ll*B[Y].m[i][j]*tmp[j]%mod)%mod;
	for(int i=1;i<=n;++i)
	    tmp[i]=Ans[i];
	for(int i=1;i<=n;++i)
	    Ans[i]=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		    Ans[i]=(Ans[i]+1ll*C[Z].m[i][j]*tmp[j]%mod)%mod;
	return Ans[u];
}
int main() {
    scanf("%d%d%d%d%d", &n, &x, &y, &t, &q);
    for (int i = 1; i <= 100000; ++i)
        A[i].clear(), B[i].clear(), C[i].clear();
    bas.clear();
    for (int i = 1; i <= n; ++i) {
        int L = max(1, i - t), R = min(n, i + t);
        int p = inv(R - L + 1);
        for (int j = L; j <= R; ++j)
            bas.m[i][j] = p;
    }
    A[0].init();
    B[0].init();
    C[0].init();
    for (int i = 1; i <= 100000; ++i)
        A[i] = A[i - 1] * bas;
    for (int i = 1; i <= 100000; ++i)
        B[i] = B[i - 1] * A[100000];
    for (int i = 1; i <= 100000; ++i)
        C[i] = C[i - 1] * B[100000];
    while (q--) {
        ll k;
        int u, v;
        scanf("%lld%d%d", &k, &u, &v);
        int X = (int) (k % 100000), Y = (int) ((k / 100000) % 100000), Z = (int) (k / 10000000000);
        int ans1 = solve(x, X, Y, Z, u), ans2 = solve(y, X, Y, Z, v);
        int ans = 1ll * ans1 * ans2 % mod;
        printf("%d\n", ans);
    }
}

5、大水题

Subtask #1

拿部分分的方法很多：暴力，找规律，简单DP（我没听懂怎么简单DP，所以就不说了 😝）

Subtask #2

正解也没听懂，待填坑

6、淘淘的集合

这题应该算比较水的了吧。

Subtask #1

大暴力，集合的处理需要并查集。预估30分（为毛我打的线段树才20分……）

Subtask #2

对于没有事件一的部分分，由于集合不合并，集合的加可以看作是单点加。我们需要一种数据结构，它支持：1、单点加 2、区间赋值 3、区间求和线段树就可以。预估40分。

Subtask #3

由于题目中有条件：保证事件4的的和不超过，因此整个操作四可以看作是个单点查询。对于操作2，我们可以对每个并查集维护一个tag，操作二就是把这个集合的tag加上一个数。对于集合的合并，我们可以采用启发式合并。合并时，将小的集合记为，大的集合记为，先将x中每个元素加上tag并减去tag[y]，再将x暴力合并到y上。总时间复杂度是注意：对于每个集合都需要维护一个数组来记录集合内的所有元素。然后我们需要……，啥都不需要，只要一个并查集预估60分。

Subtask #4

对于保证事件3的的和不超过的测试点，我们只需要加上一个单点修改就行了。但是我们不能直接将单点赋值为零，而应该赋值为，是的所在集合。因为在后面查询时改点会加上。预估80分。

Subtask #5

由于有了区间清空，可以考虑用时间戳优化。我们记表示最后一次被清空的时间（可以是第几次操作），我们不真的去清空数组，询问的答案可以转为当前的减去时的。我们需要数据结构。查询历史情况，主席树？ No。我们只需要将询问离线下来，再当前时刻就处理好以后可能用到的当前询问的值，然后就差不多了。区间修改，单点查询。线段树，分块，啥的都可以。预估100分。

std？没有。（要的话私聊我也可以，主要是不允许std复制）

7、数树

Subtask #1

骗骗分，10分左右。

Subtask #2

暴力模拟，30~45分（听说是因为出题人良心，有梯度）

Subtask #3

我们可以发现，枚举加边实际上就是枚举长度大于等于的链。

当时，我们先假设这条链是从上往下排列的，可以枚举链的上端，分两种情况讨论：

如果，则答案为

如果，则答案为

对于每个，修改就行了。

总复杂度，的分能拿满。

Subtask #4

当时，是一个菊花图，更简单。

选的连边肯定是连接两个叶子节点。连接并删环后，会剩下个单点，因此总贡献为。

因此答案就是

注意开。

总复杂度，的分也能拿满。

Subtask #5

我们还可以考虑树形DP。先枚举树根。

记为以为根的子树中任选一点，删除从到的路径的所有方案的价值之和。

记为的所有儿子节点的子树大小的乘积。

那么

复杂度为。

Subtask #6

我们会发现“横着的”链的长度都大于等于3，所以我们可以只处理“横着的”情况。

还是

那么

时间复杂度。

附上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10,MOD=998244353;
struct node{
	int v,nxt;
}edge[N<<1];
int lst[N],le;
inline void add(int u,int v){
	edge[++le].v=v,edge[le].nxt=lst[u],lst[u]=le;
	edge[++le].v=u,edge[le].nxt=lst[v],lst[v]=le;
}
int f[N],g[N],sz[N],inv[N],tans,n,tp;
void dfs(int u,int fa){
	int ans=0;
	g[u]=1,sz[u]=1;
	for (int i=lst[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if (v==fa) continue;
		dfs(v,u);
		g[u]=1ll*g[u]*sz[v]%MOD,sz[u]+=sz[v];
	}
	for (int i=lst[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if (v==fa) continue;
		ans=(1ll*f[u]*inv[sz[v]]%MOD*f[v]+ans)%MOD;
		ans+=1ll*(f[v]-g[v])*g[u]%MOD*inv[sz[v]]%MOD;
		if (ans>=MOD) ans-=MOD;
		if (ans<0) ans+=MOD;
		f[u]=(1ll*f[v]*g[u]%MOD*inv[sz[v]]+f[u])%MOD;
	}
	tans=(1ll*ans*(n==sz[u]?1ll:(n-sz[u]))+tans)%MOD;
	f[u]=(f[u]+g[u])%MOD;
}
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%d%d",&n,&tp);
	for (int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	inv[1]=1;
	for (int i=2;i<=n;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	dfs(1,0);
	printf("%d\n",tans);
	return 0;
}

SP1、非传统题

蓝蓝的程序

Task #1

很简单，就是统计最大值，最小值和总和，在生成的时候带着做就行了。

Task #2

这个求的就是矩阵中二维前缀和的总和，不开数组，一个个统计贡献就行了。

Task #3

前缀和的前缀和，还是统计贡献

Task #4

就是。

Task #5

答案就是

Task #6

将上面个式子相加，得到

故

直接高精/python求即可。

Task #7

方法同上

Task #8

方法同上（很麻烦）

Task #9

求的是给定矩阵内全子矩阵个数，用单调栈或悬线法优化即可，时间复杂度。

这题洛谷上有：

仓鼠窝

萌萌哒的Created equal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。仓鼠窝是一个由n\*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有一个2\*3的矩阵，那么1\*1的子矩阵有6个，1\*2的子矩阵有4个，1\*3的子矩阵有2个，2\*1的子矩阵有3个，2\*2的子矩阵有2个，2\*3的子矩阵有1个，所以子矩阵共有6+4+2+3+2+1=18个。可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵！第一行两个正整数n和m，分别表示仓鼠窝的行数n、列数m。接下来n行，每行m个数，每个数代表对应的格子，非0即1。若为0，表示这个格子被破坏；反之代表这个格子是完好无损的。 3 4 1 1 1 1 1 0 1 1 1 1 0 1 \_\_本题时限2s，内存限制256M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。\_\_ ```cpp No n= m= 备注 1 2 2 无 2 3 3 无 3 5 5 无 4 10 10 无 5 2000 2000 所有格子均未被破坏 6 3000 3000 所有格子均未被破坏

https://www.luogu.org/problemnew/show/P3400

Task #10

方法大致与上题相同

只是在累加答案时换成。

SP2、大数学题

二的幂

我不会（别打我），也不讲了，要题解可以私聊我。