DATE #:20240907
ITEM #:DOC
WEEK #:SATURDSY
DAIL #:捌月初伍
TAGS
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2056812613&auto=0&height=66" width="330"></iframe> < BGM = "深渊--易耀申" > < theme = oi-contest > < [NULL] > < [空] > < [空] >只有怪物才有资格被称为好人
写了一套质量真的真的很高的模拟赛题
T1 A. 数正方体
时间限制: 1 s 内存限制: 1024 MB 测评类型: 传统型
T1 数正方体
题目描述
众所周知，正方形有 4 个点,4 条边；正方体有 4 个点，12 条边，6 个面，定义点为零维基础图形，线段为一维基础图形，正方形为二维基础图形，正方体为三维基础图形...，那么请问，一个 n 维基础图形包含多少个 m 维基础图形呢 (m≤n)
多次询问，输出对 998244353 取模。
第一行输入一个正整数 T 表示数据组数。
下接 T 行，每行两个自然数 n,m，描述一组数据。
输出 T 行，每行一个数字表示答案。
对于全部数据，\(T≤105,0≤m≤n≤10^5\)
样例：
样例输入
7 3 0 3 1 3 2 3 3 48545 1 77625 77624 93574 83513样例输出
8 12 6 1 223544257 155250 424453971数据范围
对于全部数据，\(T \leq 10^5, 0 \leq m \leq n \leq 10^5\)。
- 存在 \(10 \%\) 的数据满足 \(m = 1\)
- 存在 \(10 \%\) 的数据满足 \(m = n - 1\)
- 存在 \(10 \%\) 的数据满足 \(m = 2\)
- 存在 \(10 \%\) 的数据满足 \(m=n-2\)
数学结论题，结论很优美
m 维基础图形在 n 维基础图形上的表现为，某些维取值相同，剩下维取值唯一（是个 m 维基础图形）
答案就是 \(\begin{pmatrix}n\\n−m\end{pmatrix}2^{n−m}\)
有很多种推导方式，可以直接考虑组合方案，也可以大表找规律，甚至可以通过定义使用线性代数推导。。。
非常的开拓思路
T2 B. 数连通块
时间限制: 1 s 内存限制: 1024 MB 测评类型: 传统型
题目描述
给定一个森林，每个点都有一定概率会消失，一条 \((u,v) \in \mathbb{E}\) 的边存在的条件是，\(u\) 存在且 \(v\) 存在
有若干次询问，每次给定 \([l,r]\)，然后把下标不在 \([l,r]\) 的点都删掉后，问剩余点和所有边构成的图的联通块个数的期望
输入
第一行三个整数 \(n,m,q\)，分别表示点的个数和边的个数和询问次数
之后 \(n\) 行，第 \(i\) 行有两个整数 \(a_i,b_i\)，表示第 \(i\) 个点存在的概率是 \(\frac{a_i}{b_i}\)
之后 \(m\) 行，每行有两个整数 \(u,v\)，表示存在一条连接 \(u\) 和 \(v\) 的边，保证无重边无自环
之后 \(q\) 行，每行两个整数 \([l,r]\)，表示一次询问
输出
对于每一次询问，输出一行一个整数表示答案，输出对 \(10^9+7\) 取模
样例输入
2 1 1 1 1 1 1 1 2 1 2样例输出
1数据范围
对于 \(10\%\) 的数据，保证 \(n = 10\)
对于另外 \(10\%\) 的数据，保证 \(q=1\)
对于所有数据，保证：\(1 \le n \le 10^5, 0 \le m \lt n, 1 \le q \le 10^5, 1 \le a_i \le b_i \le 10^5\)
考虑到森林中连通块个数的 \(T\) 满足：\(T=n-m\)
> 证明：每添加一条边，就会合并两个连通块，相应的，连通块的个数就会少一个 > 根据期望的线性性，可得：\(E(T)=E(n)-E(m)\)
于是问题就转化为了计算 \(E(n)\) 和 \(E(m)\)
为了方便起见，设 \(p_u\) 表示 \(u\) 的存在的概率
于是对 \(p_u\) 做前缀和数组 \(S_{p}\) 后，可得 \(E(n_{[l,r]})=S_{p_r}-S_{p_{l-1}}\)
之后只需要考虑 \(E(m)\) 如何计算，显然有：
\[E(m_{[l,r]})=\sum_{(u,v) \in \mathbb{E} \wedge u \in [l,r] \wedge v \in [l,r]} p_u \cdot p_v \]于是可以把每一条\((u,v) \in \mathbb{E}\) 的边看成一个点\((u,v)\)，它的权值是 \(p_u \cdot p_v\)
之后相当于询问一个矩形内的点的权值和，这显然就是一个二维数点问题，离线后树状数组统计即可。
重点是将问题转化成二维数点问题，转化的合理性与期望的线性性密切相关：线性性不一定一定要考虑加和，减肥同样适用
T3 C. 数大模拟
时间限制: 2 s 内存限制: 1024 MB 测评类型: 传统型
题目描述
有 \(n\) 个连续的格子，一开始某些格子上有棋子，假设格子从 \(1\) 到 \(n\) 进行编号。
你需要进行 \(k\) 轮操作，每一轮操作如下：
- 选中所有满足“其左侧相邻的是空格子”的棋子，
- 将这些棋子向左移动一格。
比如，对序列
1001101进行一轮操作后，会变为1010110（其中 \(1\) 表示这个格子上有一个棋子，\(0\) 表示这是一个空格子）。请输出操作 k\(k\) 轮后，每个格子上是否有士兵（即输出一个长度为 \(n\) 的序列，表示方式与上文相同）。
注：如果有两个相邻格子上都有棋子，那么靠右的棋子不会在这一轮操作中移动。
输入格式
第一行两个整数 \(n,k\)，分别表示格子总数与操作轮数。
第二行 \(n\) 个整数 \(\{a_n\}\)，其中 \(a_i\) 表示从左往右第 \(i\) 个格子是否有棋子（表示方式与上文相同）。
输出格式
一行 \(n\) 个整数 \(\{b_n\}\)，其中 \(b_i\) 表示操作 \(k\) 轮后，从左往右第\(i\) 个格子是否有棋子（表示方式与上文相同）。
测试样例
样例输入1
6 2 0 1 1 0 1 1样例输出1
1 1 0 1 1 0样例输入2
4 4 0 1 0 1样例输出2
1 1 0 0数据范围
对于 \(30\%\) 的数据，满足 \(n, k \le 1000\)
对于额外 \(20\%\) 的数据，满足 \(n \le 1000\)
对于 \(100\%\) 的数据，满足 \(1 \le n, k \le 10^6\)
考虑到20分的暴力有特殊性质，当轮数大于长度时，所有棋子都可以到终点
下面考虑正解
有一个长度为 \(n\) 的 \(01\) 序列，假设它叫做 \(a\)，下标从 \(1\) 开始 > > 一共要进行 \(k\) 轮操作，在每一轮中，你需要求一个 \(b\) 序列，满足： > > 若有 \(a_i=0\) 且 \(a_{i+1}=1\)，则 \(b_i=1\) 且 \(b_{i+1}=0\)，否则\(b_i=a_i\) > > 之后用 \(b\) 序列替换 \(a\) 序列
举个例子：
0 1 1 0 1 1 （初始局面）
1 0 1 1 0 1 （第一轮）
1 1 0 1 1 0 （第二轮）
1 1 1 0 1 0 （第三轮）
1 1 1 1 0 0 （第四轮）
考虑先把已经归位的 \(1\) 删除，也就是把序列一开始的前缀 \(1\) 都删掉
那么对于每一个棋子，都有一个目标距离，即最终序列的位置
显然这个最早的归位时间是最后一个棋子的归位时间
对于一个棋子，它前面每有一个棋子，则会对它产生晚归位 \(1\) 单位时间的影响
反之，它前面每有一个空格，则会对它产生早归位 \(1\) 单位时间的影响
于是就有一个求得最晚归位时间的代码了，当然也同时可以得知每个棋子的归位时间
int getlen() {
int res = 0;
for(int i = 1 ; i <= n ; ++ i) {
if(mp[i] == 0) {
int tag = 0, tot = 0;
for(int j = i ; j <= n ; ++ j) {
if(mp[j] == 1) {
++ tot;
res = max(res, (j - i + 1) - tot + tag);
}
if(mp[j] == 0) {
-- tag;
} else {
++ tag;
}
if(tag < 0) {
tag = 0;
}
}
break;
}
}
return res;
}
那么可以发现一个性质：一个棋子的晚归位时间是 \(O(n)\) 级别的
回到这个题，利用之前的打表程序再发掘一下性质
不妨让每个棋子互不相同，也就是标上标号：
0 1 2 0 3 4 （初始局面）
1 0 2 3 0 4 （第一轮）
1 2 0 3 4 0 （第二轮）
1 2 3 0 4 0 （第三轮）
1 2 3 4 0 0 （第四轮）
去掉 0\(0\)：
1 2 3 4 （初始局面）
1 2 3 4 （第一轮）
1 2 3 4 （第二轮）
1 2 3 4 （第三轮）
1 2 3 4 （第四轮）
显然有一个规律，对于数字 i\(i\) 的最后位置的这一竖条，考虑转移到 \(j=i+1\)，那么就相当于先从 \((1,j)\) 往左下角一直走，直到撞上 \(i\)，然后把 \(i\) 剩余的一段往下平移一格，然后往右平移一格
显然这个是对的，因为最终的路线一定是先撞上上一个棋子，然后和它错开一个时间格后如此操作
那么也就可以解释一开始的打表的规律了：空格会代替你撞上一次，非空格就会让你撞上一次
虽然说是要平移，但考虑每次只平移一格，而且总的轮数不会超过\(O(n)\)，所以可以用一个线段树来维护这个东西，同时用一个 \(offset\) 维护一下当前区间，于是只需要支持区间赋值上一个等差数列，区间加一，单点查询
对于查询第一次撞到哪，既可以在线段树上维护最大值，也可以二分后在线段树上跑（虽然是 \(O(\log^2 n)\) 的，但也能通过）
附上算法：
1. 找到 1 <= j <= len，满足 i - j + 1 == a[offset + 1 + j] + 1
2. 把 a[offset + 1] ~ a[offset + j] 按照 i, i - 1, i - 2, ... 的值填充
3. 把 a[offset + j + 1] ~ a[offset + len] 都 +1
4. ans[a[offset + k + 1]] = 1
实际上是模拟双端队列，手写一个 \(deque\) 就行了，时间复杂度 \(O(n)\)
T4 D. 数字符串
时间限制: 1 s 内存限制: 1024 MB 测评类型: 传统型
题目描述
有一个长度为 \(n\) 的字符串 \(S\)，对于每一个整数 \(i(1 \le i \le n)\)，求有多少个 \(x\) 满足：
- \(1 \le x \le i\)
- \(S[1,x]=S[i-x+1,i]\)
- \(x \ge i-x+1\)
- \(x-(i-x+1)+1 \equiv 0 \pmod{k}\)
以上满足条件的 x\(x\) 的数量记作 Fi\(F_i\)
输出 \(\prod_{i=1}^n (F_i+1) \text{ mod }998244353\)
输入格式
第一行一个由小写字母构成的字符串。
第二行一个整数 \(k\)，表示题目描述中的常数 \(k\)；
输出格式
一行一个整数表示答案。
样例输入
abababac 2样例输出
24样例解释
\(F\) 依次为：
0 1 0 1 0 2 0 1数据范围
subtask测试
对于 \(30\) 分的数据，满足 \(|S| \le 1000\)
对于额外 \(20\) 分的数据，满足 \(S\) 只由单一小写字母组成
对于所有数据，满足 \(1 \le k \le |S| \le 10^6\)，并且 \(S\) 仅由小写字母组成。
直接考虑求出next数组后暴力
因为数据范围的缘故，这样作时可以的
我们建立前缀树，然后在树上作差分即可
发现题目主要卡在了树上差分部分，因为对前缀树操作不熟悉，不知道怎么作差分
这套题质量真的很高，题目有不同解法，能开通不少思路
部分分的设计也很有思维含量
有没有见过的套路：期望线性性的反向应用，二维数点的转化，在前缀树上操作
//2024.9.7
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int mod = 998244353;
constexpr int oo = 100005;
int ifac[oo],fac[oo],pow2[oo];
int t,n,m;
__inline int qpow(itn a,int b){int res=1;while(b){if(b&1)(res*=a)%=mod;(a*=a)%=mod;b>>=1;}return res;}
main(void){
//fre();
fac[0] = pow2[0] = 1;
for(int i=1;i<oo;i++)pow2[i] = pow2[i-1]*2%mod;
for (itn i=1;i<oo;i++)fac[i] = fac[i-1]*i%mod;
ifac[oo-1] = qpow(fac[oo-1],mod-2);
for (itn i=oo-1;i>=1;i--)ifac[i-1] = ifac[i]*i%mod;
cin >> t;
while(t--){
cin >> n >> m;
cout << fac[n]*ifac[n-m]%mod*ifac[m]%mod*pow2[n-m]%mod << '\n';
}
exit (0);
}
//2024.9.7
//by white_ice
//#1454. 【NOIP模拟（第二套）】B. 数连通块
#include<bits/stdc++.h>
//#include"../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 1e5 + 5;
constexpr int mod = 1e9 + 7;
int n,m,q,p[oo];
__inline int qpow(itn a,itn b){int res=1;while(b){
if(b&1)(res*=a)%=mod;(a*=a)%=mod;b>>=1;}return res;}
itn sp[oo],a[oo],ans[oo];
vector<int> g[oo];
vector<pair<int,int>> que[oo];
void add(int x,itn y){for(;x;x-=x&-x)a[x]=(a[x]+y)%mod;}
itn ask(int x){itn res=0;for(;x<=n;x+=x&-x)res=(res+a[x])%mod;return res;}
main(void){
//fre();
cin >> n >> m >> q;
for(int i=1,a,b;i<=n;i++){
cin >> a >> b;
p[i]=a*qpow(b,mod-2)%mod;
sp[i]=(sp[i-1]+p[i])%mod;
}
for(int i=1,u,v;i<=m;i++){
cin >> u >> v;
if(u>v) swap(u,v);
g[v].push_back(u);
}
for(int i=1,l,r;i<=q;i++){
cin >> l >> r;
ans[i]=(sp[r]-sp[l-1])%mod;
que[r].push_back(make_pair(l,i));
}
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
add(v,p[v]*p[i]%mod);
}
for(int j=0;j<que[i].size();j++){
pair<int,int>t=que[i][j];
(ans[t.second]-=ask(t.first))%=mod;
}
}
for(int i=1;i<=q;i++)cout<<(ans[i]%mod+mod)%mod<<endl;
exit (0);
}
//2024.9.7
//by white_ice
//#1455. 【NOIP模拟（第二套）】C. 数大模拟
//wtmybzdgxsml
#include<bits/stdc++.h>
//#include"../../need.cpp"
using namespace std ;
#define itn int
constexpr int oo = 1000006;
int n,k;
bitset<oo> a,b;
int stk[oo],top;
main(void){
//fre();
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (itn c,i=1;i<=n;i++)cin >> c,a[i]=c;
itn pos = 0;
for (itn i=1;i<=n;i++){
if (!a[i]){top=max(top-1,0);continue;}
pos++;
itn cnt = 0;
for (int i=top;i>=1;i--){
if (pos-stk[i]>k)break;
cnt ++;
}
b[max(pos,i+cnt-k)] = 1;
stk[++top] = pos;
}
for (itn i=1;i<=n;i++)cout << b[i] << ' ';
exit (0);
}
//2024.9.7
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr itn oo = 1000006;
constexpr int mod = 998244353;
char ss[oo];
int k;itn ans = 1;
__inline int get2(int l,int r,int k){int pl=l/k*k,pr=r/k*k;if(pl<l) pl+=k;return (pr/k-pl/k+1);}
__inline int get1(int l,int r,int k){
if(k%2==0) return 0;
int pl = l/k*k,pr = r/k*k;
if(pl%2==0) pl+=k; else if(pl<l) pl+=2*k;
if(pr%2==0) pr-=k;
return (pr/k-pl/k)/2+1;
}
main(void){
//fre();
//cin.tie(0)->sync_with_stdio(0);
scanf("%s",ss+1);
cin >> k;
//p_(k);
function<bool(itn,int)>check=[&](itn x,int i){return ((x-(i-x+1)+1)%k)==0;};
int n = strlen(ss+1);
//p_(ss,n,2);
//p_(check(2,2));
bool flag = 1;
for(int i=2;i<=n;i++) if(ss[i] != ss[i-1]){flag = 0;break;};
if (flag){
for(int i=1;i<=n;i++){
if(i&1) (ans *= get2(1,i/2,(k%2?k:k/2))+1)%=mod;
else (ans *= get1(1,i,k)+1)%=mod;
}
}
else {
for (itn i=1;i<=n;i++){
int out = 0;
for (itn j=(i+2)/2;j<=i;j++){
if (check(j,i)){
//p_(j);
for (itn k=1;k<=j;k++){
if (ss[k]!=ss[i-j+k]) break;
if (k==j) out ++;
}
}
}
//cout << out << ' ';
(ans *= out+1)%=mod;
}
}
cout << ans << '\n';
exit (0);
}