【比賽記錄】2025CSP-S模擬賽15
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 20 | 60 | 8 | 138 | 10/21 |
A. 萬花筒
對于一條邊，假設 \(u<v\)，則會連出 \(\gcd(n,v-u)\) 個環。于是按照 kruskal 的思路，每一個環留一條邊不取即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int T,n,m;
struct node{
int u,v,w;
node(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
il bool operator<(const node &x)const{
return w<x.w;
}
}e[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
if(u>v){
swap(u,v);
}
e[i]=node(u,v,w);
}
sort(e+1,e+m+1);
int ans=0;
for(int i=1;i<=m;i++){
int d=e[i].v-e[i].u;
int t=gcd(n,d);
ans+=e[i].w*(n-t);
n=t;
}
cout<<ans<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
B. 冒泡排序趟數期望
記每一個位置 \(i\) 前比 \(p_i\) 大的有 \(num_i\) 個，那么 \(res=\max_{i=1}^{n}num_i\)。又不難發現對于每個合法的 \(num\)，都有一個唯一的 \(p\) 與之對應。于是可以枚舉 \(k\)，計算有多少個排列的 \(\max\{num_i\}=k\)。前 \(k\) 位可以亂選，后面的最大值一定為 \(k\)，所以 \(k\) 的答案即為 \(k![(k+1)^{n-k}-k^{n-k}]\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5,mod=1e9+7;
int n,fac[maxn];
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
int ans=0;
for(int i=0;i<n;i++){
(ans+=i*1ll*fac[i]%mod*(qpow(i+1,n-i)-qpow(i,n-i)+mod)%mod)%=mod;
}
cout<<ans*1ll*qpow(fac[n])%mod;
return 0;
}
}
int main(){return asbt::main();}
C. 數點
首先可以將點數的 \(k\) 次方拆成 \(j\le k\) 個點的貢獻的線性和。具體地，對于 \(k=2\)，\((a+b)^2=a^2+2ab+b^2\)，于是一個點會有 \(1\) 的貢獻，兩個點會有 \(2\) 的貢獻。\(k=3\) 是類似的。
我們分別考慮 \(j=1,2,3\) 的情況。對于 \(j=1\)，\((i,p_i)\) 的貢獻（即包含它的矩形數量）為 \(i\cdot p_i\cdot (n-i+1)\cdot (n-p_i+1)\)。這可以線性求出。
\(j=2\)，設 \(x<y\land p_x<p_y\)，貢獻為 \(x\cdot p_x\cdot (n-y+1)\cdot (n-p_y+1)\)。于是可以掃描線，將 \(x\cdot p_x\) 插入樹狀數組，在 \(y\) 查詢。對于 \(p_x>p_y\) 將數組倒過來再掃一遍即可。
\(j=3\)，分布有 \(6\) 中情況，等價下來就兩種：
枚舉中間那個點正著掃一遍再倒著掃一遍，類似的用樹狀數組即可。
容易發現第一個點貢獻左邊界，第二個點貢獻下邊界。用線段樹維護 \(\texttt{左}\times\texttt{下}\)。于是在第一個點，我們在 \(p_i\) 處給左加上 \(i\) 的貢獻；在第二個點，我們給 \([p_i+1,n]\) 的下全都加上 \(p_i\) 的貢獻；在第三個點進行區間查詢即可。注意下只能從右邊貢獻，不能來自左側。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5,mod=998244353;
int n,m,p[maxn],hp[maxn];
struct{
int tr[maxn];
il void init(){
memset(tr,0,sizeof(tr));
}
il int lowbit(int x){
return x&-x;
}
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
(tr[p]+=v)%=mod;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
(res+=tr[p])%=mod;
}
return res;
}
}F;
struct node{
int a,sum;
node(int a=0,int sum=0):a(a),sum(sum){}
il node operator+(const node &x)const{
return node((a+x.a)%mod,(sum+x.sum)%mod);
}
};
struct{
int tag[maxn<<2];
node tr[maxn<<2];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int v){
(tag[id]+=v)%=mod;
(tr[id].sum+=tr[id].a*v)%=mod;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
tr[id]=node(),tag[id]=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void add(int id,int l,int r,int p,int v){
if(l==r){
(tr[id].a+=v)%=mod;
tr[id].sum=tag[id]=0;
return ;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid){
add(lid,l,mid,p,v);
}
else{
add(rid,mid+1,r,p,v);
}
pushup(id);
}
il void mul(int id,int L,int R,int l,int r,int v){
if(l>r){
return ;
}
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
mul(lid,L,mid,l,r,v);
}
if(r>mid){
mul(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr[id].sum;
}
pushdown(id);
int mid=(L+R)>>1,res=0;
if(l<=mid){
(res+=query(lid,L,mid,l,r))%=mod;
}
if(r>mid){
(res+=query(rid,mid+1,R,l,r))%=mod;
}
return res;
}
}S;
il int calc1(){
int res=0;
for(int i=1;i<=n;i++){
(res+=i*p[i]*(n-i+1)%mod*(n-p[i]+1))%=mod;
}
return res;
}
il int calc2(){
int res=0;
F.init();
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*F.query(p[i]))%=mod;
F.add(p[i],i*p[i]%mod);
}
reverse(p+1,p+n+1);
F.init();
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*F.query(p[i]))%=mod;
F.add(p[i],i*p[i]%mod);
}
return res;
}
il int calc3(){
int res=0;
F.init();
for(int i=1;i<=n;i++){
hp[i]=F.query(p[i]);
F.add(p[i],i*p[i]%mod);
}
F.init();
for(int i=n;i;i--){
(res+=hp[i]*(F.query(n)-F.query(p[i])+mod))%=mod;
F.add(p[i],(n-i+1)*(n-p[i]+1)%mod);
}
reverse(p+1,p+n+1);
F.init();
for(int i=1;i<=n;i++){
hp[i]=F.query(p[i]);
F.add(p[i],i*p[i]%mod);
}
F.init();
for(int i=n;i;i--){
(res+=hp[i]*(F.query(n)-F.query(p[i])+mod))%=mod;
F.add(p[i],(n-i+1)*(n-p[i]+1)%mod);
}
S.build(1,1,n);
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*S.query(1,1,n,1,p[i]))%=mod;
S.add(1,1,n,p[i],i);
S.mul(1,1,n,p[i]+1,n,p[i]);
}
reverse(p+1,p+n+1);
S.build(1,1,n);
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*S.query(1,1,n,1,p[i]))%=mod;
S.add(1,1,n,p[i],i);
S.mul(1,1,n,p[i]+1,n,p[i]);
}
for(int i=1;i<=n;i++){
p[i]=n-p[i]+1;
}
S.build(1,1,n);
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*S.query(1,1,n,1,p[i]))%=mod;
S.add(1,1,n,p[i],i);
S.mul(1,1,n,p[i]+1,n,p[i]);
}
reverse(p+1,p+n+1);
S.build(1,1,n);
for(int i=1;i<=n;i++){
(res+=(n-i+1)*(n-p[i]+1)%mod*S.query(1,1,n,1,p[i]))%=mod;
S.add(1,1,n,p[i],i);
S.mul(1,1,n,p[i]+1,n,p[i]);
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>p[i];
}
int ans=0;
switch(m){
case 1:{
ans=calc1();
break;
}
case 2:{
ans=(calc1()+2*calc2())%mod;
break;
}
default:{
ans=(calc1()+6*calc2()+6*calc3())%mod;
break;
}
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號