题解：AT_arc168_c [ARC168C] Swap Characters

· · 题解

Sol

感觉不是很简单吧。

考虑刻画最后形成的序列的特征，不难想到将同字符的位置划作一类，然后三类中各选出一些位置与其余两类交换这样子。

更精准地刻画这个东西，考虑将变化视作一次连边，如一个位置本来是 A 后来变为 B，就使 A 到 B 的边权自增一。那么我们就可以得到一种变换，这种变换由“某个字符变了多少位置到另某个字符”的限制组成，那么计算一种变换对应的最终序列个数是简单的，计 xy 为字符 x 变为 y 的位置个数，那么由多重组合数可得 \binom{cnt_a}{ab,ac}\binom{cnt_b}{ba,bc}\binom{cnt_c}{ca,cb} 即为对应的序列个数，意义显然。

考虑判断一种变换是否合法，也就是看能否在 k 次操作以内变出来。

可以发掘几个性质，首先三个点各自的入度等于出度，因为字符串中各字符数量恒定不变。其次，从最终状态来看，不难发现有效交换只会有两种：两两互换和三个轮换。并且，从最终状态来看，这两种交换显然是相互独立的。

那么我们可以先把每对之间可能的两两互换都消除，那么剩下的图必然是一个边权全部相等的有向环，边权全部相等是由于入度等于出度的性质。这么贪心显然是最优的，因为每一步操作都是有效的交换。

那么我们就可以枚举六条边的边权得到变换然后计算贡献了，但由于入度等于出度的性质，不难发现只需要枚举四条即可，最后复杂度为 O(k^4)。

Code

const int N=2.5e5+5,K=105;

int n,k;
string s;
int a,b,c;
mint fc[N],iv[N],ans;
#define C(n,m1,m2) (fc[n]*iv[m1]*iv[m2]*iv[n-m1-m2])

inline void Main(){
    cin>>n>>k>>s;
    fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
    iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;
    for(auto i:s)a+=(i=='A'),b+=(i=='B'),c+=(i=='C');
    rep(ab,0,min(k,a))rep(ac,0,min(k,a-ab))rep(bc,0,min(k,b))rep(cb,max(0,bc-ab),min(k,ac+bc)){
        int ba=ab+cb-bc,ca=ac+bc-cb;
        if(ba+bc>b||ca+cb>c)continue;
        auto chk=[&](int a,int b,int c,int d,int e,int f){
            int x=min(a,b),y=min(c,d),z=min(e,f);
            a-=x,b-=x,c-=y,d-=y,e-=z,f-=z;
            return x+y+z+2*(a+b)<=k;
        };if(!chk(ab,ba,ac,ca,bc,cb))continue;
        ans+=C(a,ab,ac)*C(b,ba,bc)*C(c,ca,cb);
    }
    put(ans);
}