【比賽記錄】2025CSP-S模擬賽60
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 32 | 50 | 0 | 132 | 15/24 |
A. 數列變換
\(f(j)=\left|\sum_{i=1}^{n}(-1)^{i-1} a_{i}-(-1)^{i-1} b_{i+j}\right|=\left|\sum_{i=1}^{n}(-1)^{i-1} a_{i}+\sum_{i=1}^{n}(-1)^{i} b_{i+j}\right|\)，前一項和 \(j\) 沒關系，可以 \(O(1)\) 維護變化，后一項直接預處理出來即可。然后二分一下就好了。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,m,q,a[maxn],b[maxn];
set<int> st;
il void calc(int x){
auto it=st.lwrb(x);
if(it==st.begin()){
cout<<*it-x<<'\n';
}else if(it==st.end()){
cout<<x-*prev(it)<<'\n';
}else{
cout<<min(*it-x,x-*prev(it))<<'\n';
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
b[i]=b[i-1]+(i&1?-b[i]:b[i]);
}
for(int i=0;i<=m-n;i++){
st.insert(i&1?b[i]-b[i+n]:b[i+n]-b[i]);
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=i&1?a[i]:-a[i];
}
calc(-ans);
while(q--){
int l,r,x;
cin>>l>>r>>x;
if((r-l)%2==0){
ans+=l&1?x:-x;
}
calc(-ans);
}
return 0;
}
}
signed main(){return asbt::main();}
B. 排列計數
首先可以轉化成將一對帶標號小球排列且滿足相鄰小球顏色不同的方案數。
記顏色數為 \(m\)，第 \(i\) 中顏色有 \(s_i\) 個，連成了 \(b_i\) 塊。記 \(B=\sum b_i\)。此時的方案數為 \(\frac{B!}{\prod_{i=1}^{m}b_i!}\prod_{i=1}^{m}s_i!{s_i-1\choose b_i-1}\)。
設 \(f_{i,j}\) 為考慮了前 \(i\) 個顏色時 \(\sum b=j\)，\(\prod_{k=1}^{i}{s_k-1\choose b_k-1}\frac{1}{b_k!}\) 的值，容易 DP 求出。于是根據容斥，答案為：
\[\prod_{i=1}^{m}s_i!\sum_{j=m}^{n}j!f_{m,j}(-1)^{n-j}
\]
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int mod=1e9+7;
int T,n,a[605],f[605][605],s[605];
int fac[605],inv[605],lsh[605];
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
y>>=1,x=x*1ll*x%mod;
}
return res;
}
il void init(int n=600){
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n]);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
il int C(int x,int y){
if(x<y||y<0){
return 0;
}
return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
init();
while(T--){
cin>>n;
int tot=0;
for(int i=1;i<=n;i++){
cin>>a[i];
int x=a[i];
a[i]=1;
for(int j=2;j<=x/j;j++){
if(x%j==0){
int num=0;
while(x%j==0){
x/=j,num++;
}
if(num&1){
a[i]*=j;
}
}
}
if(x>1){
a[i]*=x;
}
lsh[++tot]=a[i];
// cout<<a[i]<<' ';
}
// cout<<'\n';
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=tot;i++){
s[i]=0;
}
for(int i=1;i<=n;i++){
a[i]=lwrb(lsh+1,lsh+tot+1,a[i])-lsh;
s[a[i]]++;
}
for(int i=0;i<=tot;i++){
for(int j=0;j<=n;j++){
f[i][j]=0;
}
}
f[0][0]=1;
for(int i=1,ss=0;i<=tot;i++){
ss+=s[i];
for(int j=1;j<=ss;j++){
for(int k=1;k<=min(s[i],j);k++){
f[i][j]=(f[i-1][j-k]*1ll*C(s[i]-1,k-1)%mod*inv[k]+f[i][j])%mod;
}
}
}
int ans=0;
for(int i=tot;i<=n;i++){
if((n-i)&1){
ans=(ans-f[tot][i]*1ll*fac[i]%mod+mod)%mod;
}else{
ans=(f[tot][i]*1ll*fac[i]+ans)%mod;
}
}
for(int i=1;i<=tot;i++){
ans=ans*1ll*fac[s[i]]%mod;
}
cout<<ans<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號