2025.1.19 计数杂题选讲

· · 个人记录

#1176. 114514

设 p_i 表示 a_1 到 a_i 中不存在 p_i，但 p_i+1 到 a_i 都存在。

如果 x\leq b_i 放在位置 i，那么可以将 a_j(j>i) 与 a_i 换位置，字典序变得更小，矛盾。

所以位置 i 只能放 b_i<x\leq a_i，组合意义一下。 

#include <bits/stdc++.h>
using namespace std;
const int N=4e6+5;
const int mod=1e9+7;
int n,a[N],ans=1,fa[N];
bool vis[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    freopen("trans.in","r",stdin);
    freopen("trans.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=N-5;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        vis[a[i]]=1;
        if(vis[a[i]-1])merge(a[i],a[i]-1);
        if(vis[a[i]+1])merge(a[i]+1,a[i]);
        ans=1ll*ans*(a[i]-find(a[i])+1)%mod;
    }
    printf("%d",ans);
    return 0;
}

A. 数学

发现对于每一个 [1,i] 的区间，里面的数都是连续的。

枚举 p_x，组合意义。

#include <bits/stdc++.h>
using namespace std;
const int N=2e7+5; 
const int inf=2e7;
const int mod=998244353;
int n,s,x,l,r,ans=0,fac[N],inv[N];
int ksm(int a,int b){
    int sum=1;
    while(b){
        if(b&1)sum=1ll*sum*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return sum;
}
int c(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return 1ll*(1ll*fac[n]*inv[m]%mod)*inv[n-m]%mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    fac[0]=inv[0]=1;
    for(int i=1;i<=inf;i++)fac[i]=1ll*fac[i-1]*i%mod;
    inv[inf]=ksm(fac[inf],mod-2);
    for(int i=inf-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    cin >>n>>s>>x>>l>>r;
    if(x==1){
        if(l<=s&&s<=r){
            cout <<c(s-1+n-s,s-1);
        }else cout <<0;
        return 0;
    }
    for(int i=l;i<=r;i++){
        if(i<s){
            int dis=s-i;
            if(dis>x-1||i+x-1>n)continue;
            int cnt=(x-1)-dis;
            dis--;
            ans=(ans+1ll*c(cnt+dis,dis)*c(i-1+n-(i+x-1),i-1)%mod)%mod;
        }
        if(i>s){
            int dis=i-s;
            if(dis>x-1||i-x+1<=0)continue;
            int cnt=(x-1)-dis;
            dis--;
            ans=(ans+1ll*c(cnt+dis,dis)*c(n-i+i-x,i-x)%mod)%mod;
        }
    }
    cout <<ans;
    return 0;
}

#578. Divide a Sequence

设 dp_i 为以 i 结尾的所有方案价值总和。

dp_i=\sum\limits_{j=1}^{i} dp_{j-1}\times(\max\limits_{k=j}^i a_k-\min\limits_{k=j}^i a_k)

发现 \max 和 \min 可以分开计算。

单调栈。

将最值相同的 dp 值合并。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int n,a[N],dp[N],maxn[N],minn[N];
deque<int>q[3];
signed main(){
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >>a[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){
        while(!q[1].empty()&&a[q[1].front()]<a[i]){
            q[1].pop_front();
        }
        while(!q[2].empty()&&a[q[2].front()]>a[i]){
            q[2].pop_front();
        }
        if(!q[1].empty()){
            maxn[i]=(maxn[q[1].front()]+(dp[i-1]-dp[q[1].front()-1]+mod)%mod*a[i]%mod)%mod;
        }else{
            maxn[i]=dp[i-1]*a[i]%mod;
        }
        if(!q[2].empty()){
            minn[i]=(minn[q[2].front()]+(dp[i-1]-dp[q[2].front()-1]+mod)%mod*a[i]%mod)%mod;
        }else{
            minn[i]=dp[i-1]*a[i]%mod;
        }
        dp[i]=(dp[i-1]+maxn[i]-minn[i]+mod)%mod;
        q[1].push_front(i);
        q[2].push_front(i);
    }
    cout <<(dp[n]-dp[n-1]+mod)%mod;
    return 0;
}

#580. Yet Another Path Counting

只能往下往右走，问开头结尾颜色相同的路径有几种。

根号分治。

对于颜色个数少于 n，直接暴力求。

其他的 dp 求。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5;
const int inf=2e3;
const int mod=998244353;
int n,a[N][N],f[N][N],fac[N],inv[N],ans=0;
vector<pair<int,int> >pos[N*N]; 
int ksm(int a,int b){
    int sum=1;
    while(b){
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
int c(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return (fac[n]*inv[m]%mod)*inv[n-m]%mod;
}
int calc(int n,int m){
    return c(n+m,n);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >>n;
    fac[0]=1;
    for(int i=1;i<=inf;i++)fac[i]=fac[i-1]*i%mod;
    inv[inf]=ksm(fac[inf],mod-2);
    for(int i=inf-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >>a[i][j];
            pos[a[i][j]].push_back(make_pair(i,j));
        }
    }
    for(int i=1;i<=n*n;i++){
        if(pos[i].size()<=n){
            for(int j=0;j<pos[i].size();j++){
                for(int k=0;k<pos[i].size();k++){
                    if(j==k)continue;
                    if(pos[i][j].first<=pos[i][k].first&&pos[i][j].second<=pos[i][k].second){
                        ans+=calc(pos[i][k].first-pos[i][j].first,pos[i][k].second-pos[i][j].second);
                        ans%=mod;
                    }
                }
            }
            ans=(ans+pos[i].size())%mod; 
        }else{
            for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)f[j][k]=0;
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    f[j][k]+=f[j-1][k],f[j][k]+=f[j][k-1];
                    if(a[j][k]==i)f[j][k]++,ans+=f[j][k];
                    f[j][k]%=mod,ans%=mod;
                }
            }
        }
    }
    cout <<ans<<"\n";
    return 0;
}

#858. 神眷

考虑如果划分成多段合法，那么划分成两端一定合法。

为了计算不重不漏，所以分割点是该序列所有分割点的最前一个才计算。

\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times (2^{n-i}-1)^j\times ((2^i-1)^j-(2^i-2)^j) =\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times (2^{n-i}-1)^j\times (2^i-1)^j-\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times (2^{n-i}-1)^j\times(2^i-2)^j =\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times ((2^{n-i}-1)\times (2^i-1))^j-\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times ((2^{n-i}-1)\times(2^i-2))^j

二项式定理：(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^ib^{n-i}

\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times ((2^{n-i}-1)\times (2^i-1))^j\times 1^{k-j}-\sum\limits_{i=1}^{n-1} \sum\limits_{j=0}^k \binom{k}{j} \times ((2^{n-i}-1)\times(2^i-2))^j\times 1^{k-j} = \sum\limits_{i=1}^{n-1} ((2^{n-i}-1)\times (2^i-1)+1)^k-\sum\limits_{i=1}^{n-1} ((2^{n-i}-1)\times (2^i-2)+1)^k

最后加上全零序列的方案即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int n,k,ans=1;
int ksm(int a,int b){
    int sum=1;
    while(b){
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
signed main(){
    freopen("god.in","r",stdin);
    freopen("god.out","w",stdout);
    cin >>n>>k;
    for(int i=1;i<=n;i++){
        int a=ksm((ksm(2,i)-1)*(ksm(2,n-i)-1)%mod+1,k);
        int b=ksm((ksm(2,i)-2)*(ksm(2,n-i)-1)%mod+1,k);
        ans=(ans+a-b+mod)%mod;
    }
    int p=ksm(ksm(2,k),n);
    cout <<ans*ksm(p,mod-2)%mod;
    return 0;
}