Codeforces 1111D Destroy the Colony

题目链接https://codeforces.com/problemset/problem/1111/D

题意:简化版题意,有52个字符,用a[x]代表字符x的数量,已经\sum_{i=1}^{52}a[i]=n,保证n是偶数,现在要你选一个子集使得和为n/2,另一个子集也为n/2,同时每次询问限制xy字符必须在同一个子集里,还有一个是确定好两个子集以后里面怎么放也是未知的,求方案数。

思路:假设我们当前已经有两个子集,那么这个时候的答案是多少呢?考虑多重集合的排列我们可以直接得到这个答案是固定的。那么其实问题就转化为求选一个子集使得和为n/2的方案数,不考虑询问是一个裸的01背包,然后注意到本质不同的询问只有52*52种,所以我们只要预处理出所有询问的答案即可,直接枚举所有所有答案对然后去跑01背包是O(nk * k^2)的,无法通过,但是我们可以考虑先预处理出没有限制的背包答案,然后xy必须在同一个子集里其实就是相当于删除这两个物品的过程,所以枚举答案对然后删除物品xy就可以让复杂度去掉一个k,即O(nk^2)就可以通过了,Claris讲了一个复杂度更低的做法表示没有看懂....

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
const int P=1e9+7;
int q,n,i,j,k,x,y,w,f[N],dp[N],inv[N],fac[N],buc[100],ans[100][100];
char s[N];
int fexp(int a,int n){
    int res=1;
    while (n){
        if (n&1) res=1LL*res*a%P;
        a=1LL*a*a%P;
        n>>=1;
    }
    return res;
}
int convert(char ch){
    if (ch>='a' && ch<='z') return ch-'a'+1;
    return ch-'A'+27;
}
inline void up(int&a,int b){a+=b==P?0:b;if(a>=P)a-=P;}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for (i=1;i<=n;++i) buc[convert(s[i])]++;
    for (fac[0]=i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%P;
    inv[n]=fexp(fac[n],P-2);
    for (i=n-1;i>=0;--i) inv[i]=1LL*inv[i+1]*(i+1)%P;
    w=1LL*fac[n/2]*fac[n/2]%P;
    for (i=1;i<=52;++i) w=1LL*w*inv[buc[i]]%P;
    for (dp[0]=1,i=1;i<=52;++i)if(buc[i]){
        for (j=n/2;j>=buc[i];--j){
            up(dp[j],dp[j-buc[i]]);
        }
    }
    for (i=1;i<=52;++i) ans[i][i]=1LL*w*dp[n/2]%P;
    for (i=1;i<=52;++i)if(buc[i]){
        for (k=0;k<=n/2;++k) f[k]=dp[k];
        for (k=buc[i];k<=n/2;++k) up(f[k],P-f[k-buc[i]]);
        for (j=i+1;j<=52;++j)if(buc[j]){
            for (k=buc[j];k<=n/2;++k) up(f[k],P-f[k-buc[j]]);
            ans[i][j]=ans[j][i]=2LL*w%P*f[n/2]%P;
            for (k=n/2;k>=buc[j];--k) up(f[k],f[k-buc[j]]);
        }
    }
    for (read(q);q--;){
        read(x),read(y);
        x=convert(s[x]),y=convert(s[y]);
        printf("%d\n",ans[x][y]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注