day 3 模拟赛 2
模拟赛 2
T1 思维碰撞（thinking）
给定一个序列 a，求随机选择序列中的一个连续区间，这个区间中相同数组数的期望值，\(n\le 10^5,a_i\le2^{32}-1\)。
暴力：枚举区间端点 l,r，每次向右拓展新的 r 的时候，之后每次需要增加的贡献会增加 \(cnt[a[r]]\)，时间复杂度 \(O(n^2)\)。-------------------------------68分
考虑如何优化。
我们可以先对序列进行离散化，把值域转化为与 n 同阶，然后枚举 x，预处理出 x 出现的所有位置 \(p_{x[i]}\)，那么数字 x 对最终答案的贡献就是 \(\sum_{i<j} p_{x[i]}(n-p_{x[j]+1})\)。
这个式子可以化简成 \(\sum_{j=2}^k[(n-p_j+1)\sum_{i=1}^{j-1}p_i]\)，其中 \(\sum_{i=1}^{j-1}p_i\) 可以运用前缀和快速计算，只需遍历一次 j 即可，时间复杂度 \(O(n)\)。------------------------100分
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
map<int,vector<int>>mp;
signed main(){freopen("thinking.in","r",stdin);freopen("thinking.out","w",stdout);ios::sync_with_stdio(0);cin.tie();cin>>n;for(int i=1;i<=n;++i){int x;cin>>x;mp[x].push_back(i);}int sum=0;for(auto& e:mp){auto& v=e.second;int pre=0;for(int p:v){sum+=pre*(n-p+1);pre+=p;}}int tot=n*(n+1)/2;double ans=1.0*sum/tot;printf("%.6f",ans);return 0;
}
T2 断桥日出（sunrise）
对一个序列长度为 n，进行以下 m 次操作（\(n,m\le 10^5\)）：
0 l r x：区间 \([l,r]\) 乘上 x1 l r求区间 \([l,r]\) 的和欧拉函数和欧拉函数：\(\phi(n)\) 为 1~n 与 n 互质的数的个数。
暴力：每次修改、询问 \(O(n)\) 地进行操作，时间复杂度 \(O(n^2)\)，可以通过 \(n,m\le 1000\)。------------------------30分
对于没有修改的数据，只有查询区间和，考虑运用线段树，先预处理出每个数的欧拉函数值，再用线段树区间查询即可。------------------------40分
接下来，考虑数 a 乘上 b 后，\(\phi (a)\) 会发生什么变化，打表欧拉函数结果如下：
1 1
2 1
3 2
4 2
5 4
6 2
7 6
8 4
9 6
10 4
11 10
12 4
13 12
14 6
15 8
16 8
17 16
18 6
19 18
20 8
我们发现，当 \(a\mod b=0\) 时，\(\phi(ab)=\phi(a)*b\)，当 \(a\mod b≠0\) 时，\(\phi(ab)=\phi(a)*(b-1)\)，观察 \(a_i=x=2\) 的部分分，发现总是满足第一种情况，所以线段树的修改操作，可以直接替换为区间乘 x。-------------------55分
考虑如何让线段树实现两种情况。我们可以在线段树上维护当前区间是否满足每个数都有因子 \(p\)，因为通过 \(x\le 100\) 的数据范围中，我们意识到 100 中的质数只有 25 个，所以因子的种类也只有 25 个，可以直接用二进制状压，在线段树中记作mask。
那么，在修改操作中，我们可以先对 x 进行质因数分解，使得每次修改操作都乘上质数，然后在线段树上走的过程中，如果走到的区间所有数都包含这个质因子，就不用向下走了，直接打上标记即可，最终复杂度 \(O(25n+n\log n)\)。-------------------100分
#include<bits/stdc++.h>
#define ls u*2
#define rs u*2+1
#define mid (l+r)/2
#define int long long
using namespace std;
int n,m;
int a[100005];
const int mod=998244353;
struct tree{int sum,mask,lazy;
}tr[400005];
int prim[50]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int phi(int x){int res=x;int tmp=x;for(int i=1;i<=25;i++){int p=prim[i];if(p*p>tmp) break;if(tmp%p==0){res=res/p*(p-1);while(tmp%p==0)tmp/=p;}}if(tmp>1)res=res/tmp*(tmp-1);return res%mod;
}
void build(int u,int l,int r){tr[u].lazy=1;if(l==r){tr[u].sum=phi(a[l]);tr[u].mask=0;int tmp=a[l];for(int i=1;i<=25;i++){int p=prim[i];if(tmp%p==0){tr[u].mask|=1LL<<i;while(tmp%p==0)tmp/=p;}}return;}build(ls,l,mid);build(rs,mid+1,r);tr[u].sum=(tr[ls].sum+tr[rs].sum)%mod;tr[u].mask=tr[ls].mask&tr[rs].mask;
}
void push_down(int u){if(tr[u].lazy==1)return;tr[ls].sum=tr[ls].sum*tr[u].lazy%mod;tr[ls].lazy=tr[ls].lazy*tr[u].lazy%mod;tr[rs].sum=tr[rs].sum*tr[u].lazy%mod;tr[rs].lazy=tr[rs].lazy*tr[u].lazy%mod;tr[u].lazy=1;
}
void update(int u,int l,int r,int L,int R,int k){int p=prim[k];if(L<=l&&r<=R){if(tr[u].mask&(1LL<<k)){tr[u].sum=tr[u].sum*p%mod;tr[u].lazy=tr[u].lazy*p%mod;return;}if(l==r){tr[u].sum=tr[u].sum*(p-1)%mod;tr[u].mask|=1LL<<k;a[l]*=p;return;}}push_down(u);if(L<=mid) update(ls,l,mid,L,R,k);if(R>mid) update(rs,mid+1,r,L,R,k);tr[u].sum=(tr[ls].sum+tr[rs].sum)%mod;tr[u].mask=tr[ls].mask&tr[rs].mask;
}
int query(int u,int l,int r,int L,int R){if(L<=l&&r<=R)return tr[u].sum%mod;push_down(u);if(L>mid)return query(rs,mid+1,r,L,R);if(R<=mid)return query(ls,l,mid,L,R);return (query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R))%mod;
}signed main(){ freopen("sunrise.in","r",stdin);freopen("sunrise.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(m--){int op,l,r,x;cin>>op;if(op==0){cin>>l>>r>>x;int tmp=x;for(int i=1;i<=25;i++){int p=prim[i];while(tmp%p==0){update(1,1,n,l,r,i);tmp/=p;}}}else{cin>>l>>r;cout<<query(1,1,n,l,r)<<"\n";}}return 0;
}
T3 长夜启明（dawn）
高楼有 n 层，每层是有 k 个点的多边形，其中有 m 盏是关键的，必须点亮，其余可点亮可关闭，每一层相邻的两盏灯不能同时打开，相邻两层相同位置的等不能同时打开，求总开关方案数模 998244353 的结果。
\(n\le10^{18},m\le 50,3\le k\le 11\)
先考虑 n 较小的情况，我们发现 k 始终很小，考虑状压 DP，把 k 个灯的开关状态压缩成二进制数，一层一层进行转移。-------------------35分
当 n 较大时，考虑如何转移，容易想到矩阵乘法。
为什么？先不考虑关键的灯，我们可以得到一个转移矩阵，即枚举所有的单层状态，大约 \(2^{11}=2048\) 个，这个矩阵的 i 行 j 列记录状态 i 和状态 j 相邻是否合法，设合法的单层状态为 G，那么这个矩阵有 G 行 G 列。
转移一次，只需进行一次矩阵乘法，考虑如何快速进行大量转移。尝试倍增，每次向上跳 \(2^i\) 层，我们先预处理出跳 \(2^i\) 层需要乘的矩阵，也就是转移矩阵的 i 次方，然后我们只需要一次乘法就能跳一次，矩阵乘法复杂度 \(O(G^3)\)，倍增最多跳 \(\log n\) 次，可以通过本题。-------------------60分
现在就差如何处理关键灯，很简单，关键灯很少，所有我们一段一段倍增，每次遇到有关键灯的层单独处理，注意要预处理出每一层关键灯的集合。
最终复杂度 \(O(G^3\log n+mG^2\log n)\)。-------------------100分
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,cnt;
map<int,int>must;
int id[2100],ok[505];
int t[505][505];
int powt[70][505][505];
const int mod=998244353;
int dp[505];
int nxt[505];
void jump(int h){int bit=0;while(h>0){if(h&1){for(int i=0;i<cnt;i++) nxt[i]=0;for(int i=0;i<cnt;i++){if(dp[i]==0) continue;for(int j=0;j<cnt;j++){if(powt[bit][i][j]==0) continue;nxt[j]=(nxt[j]+dp[i]*powt[bit][i][j])%mod;}}for(int i=0;i<cnt;i++) dp[i]=nxt[i];}h/=2;bit++;}
}
signed main(){freopen("dawn.in","r",stdin);freopen("dawn.out","w",stdout);cin>>n>>m>>k;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;must[a]|=(1<<(b-1));}for(int s=0;s<(1<<k);s++){bool flag=1;for(int i=0;i<k;i++){if((s&(1<<i))&&(s&(1<<((i-1+k)%k)))){flag=0;break;}}if(flag){id[s]=cnt;ok[cnt]=s;cnt++;}}for(int i=0;i<cnt;i++){for(int j=0;j<cnt;j++){if((ok[i]&ok[j])==0) t[i][j]=1;else t[i][j]=0;}}for(int i=0;i<cnt;i++){for(int j=0;j<cnt;j++){powt[0][i][j]=t[i][j];}}for(int p=1;p<=65;p++){for(int i=0;i<cnt;i++){for(int mid=0;mid<cnt;mid++){if(powt[p-1][i][mid]==0) continue;for(int j=0;j<cnt;j++){if(powt[p-1][mid][j]==0) continue;powt[p][i][j]=(powt[p][i][j]+powt[p-1][i][mid]*powt[p-1][mid][j])%mod;}}}}for(int i=0;i<cnt;i++) dp[i]=1;int h=1;for(auto it=must.begin();it!=must.end();it++){if(it->first>h){jump(it->first-h);}for(int i=0;i<cnt;i++){if((ok[i] & it->second)!=it->second)dp[i]=0;}h=it->first;}if(n>h)jump(n-h);int ans=0;for(int i=0;i<cnt;i++) ans=(ans+dp[i])%mod;cout<<ans;return 0;
}