2020-2021:teams:legal_string:lgwza:可逆背包
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:可逆背包 [2021/07/16 15:12] lgwza |
2020-2021:teams:legal_string:lgwza:可逆背包 [2021/07/16 22:58] (当前版本) lgwza |
||
|---|---|---|---|
| 行 68: | 行 68: | ||
| } | } | ||
| return 0; | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 例 2 ==== | ||
| + | |||
| + | [[https://codeforces.com/contest/1111/problem/D|CF 1111 D. Destroy the Colony]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一个长度为偶数的由大小写字母组成的字符串 $s$，一个“好”字符串可通过重排字母顺序使得所有相同字母的位置都在 $s$ 的同一半（$[1,n/2] or [n/2+1,n]$）来生成。$q$ 个询问，给定一对 $(i,j)$，要求字母 $s[i],s[j]$ 也在 $s$ 的同一半的“好”字符串数量。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 注意到询问本质上最多只有 $52^2$ 种可能，则考虑先把所有询问算出来，最后 $O(1)$ 回答询问。 | ||
| + | |||
| + | - 令 $k$ 为字母种数，统计各字母的出现次数 $c_1,c_2,\cdots,c_k$，若有 $i_1,i_2,\cdots,i_p$ 使得 $c_{i_1}+c_{i_2}+\cdots+c_{i_p}=\dfrac{n}{2}$，则把它们放到第一组，剩下的放到第二组，第一组的排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{i_1}!c_{i_2}!\cdots c_{i_p}!}$，第二组排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{j_1}!c_{j_2}!\cdots c_{j_s}!}$，总方法数为 $W=\dfrac{(\dfrac{n}{2})!(\dfrac{n}{2})!}{c_1!c_2!\cdots c_k!}$； | ||
| + | - 注意到 $c_i$ 求和为 $\dfrac{n}{2}$ 的组合数可用 01 背包来求，在没有 $(i,j)$ 限制下的“好”字符串数量为 $W*dp[n/2]*2$； | ||
| + | - 现考虑 $(i,j)$ 的限制，即字母 $s[i]$ 和 $s[j]$ 需在同一组中，等价于去掉字母 $s[i]$ 和 $s[j]$ 的 01 背包问题，即作了一次 01 背包问题后，再枚举 $i,j$ 做退背包过程，将去掉 $(i,j)$ 的 DP 值记作 $ans[i][j]$； | ||
| + | - 最后对每个询问直接 $O(1)$ 输出答案即可。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=1e5+5,mod=1e9+7; | ||
| + | typedef long long ll; | ||
| + | ll fastpow(ll x,ll y){ | ||
| + | ll ret=1; | ||
| + | for(;y;x=x*x%mod,y>>=1) | ||
| + | if(y&1) ret=ret*x%mod; | ||
| + | return ret; | ||
| + | } | ||
| + | int conv(int x){ | ||
| + | if(x>='a') return x-'a'+26; | ||
| + | return x-'A'; | ||
| + | } | ||
| + | ll dp[N],fac[N],inv[N],temp_dp[N]; | ||
| + | ll ans[55][55]; | ||
| + | ll w[55]; | ||
| + | int main(){ | ||
| + | string s; | ||
| + | cin>>s; | ||
| + | int n=s.length(); | ||
| + | fac[0]=1; | ||
| + | w[conv(s[0])]++; | ||
| + | for(int i=1;i<n;i++){ | ||
| + | w[conv(s[i])]++; | ||
| + | fac[i]=fac[i-1]*i%mod; | ||
| + | } | ||
| + | fac[n]=fac[n-1]*n%mod; | ||
| + | inv[n]=fastpow(fac[n],mod-2); | ||
| + | for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; | ||
| + | ll W=fac[n/2]*fac[n/2]%mod; | ||
| + | for(int i=0;i<52;i++){ | ||
| + | if(w[i]) W=W*inv[w[i]]%mod; | ||
| + | } | ||
| + | dp[0]=1; | ||
| + | for(int i=0;i<52;i++){ | ||
| + | if(w[i]){ | ||
| + | for(int j=n;j>=w[i];j--){ | ||
| + | dp[j]=(dp[j]+dp[j-w[i]])%mod; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | for(int i=0;i<52;i++) ans[i][i]=dp[n/2]; | ||
| + | for(int i=0;i<52;i++){ | ||
| + | if(!w[i]) continue; | ||
| + | for(int k=0;k<=n;k++) temp_dp[k]=dp[k]; | ||
| + | |||
| + | for(int k=w[i];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[i]]+mod)%mod; | ||
| + | for(int j=i+1;j<52;j++){ | ||
| + | if(!w[j]) continue; | ||
| + | for(int k=w[j];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[j]]+mod)%mod; | ||
| + | ans[i][j]=2ll*temp_dp[n/2]%mod; | ||
| + | ans[j][i]=ans[i][j]; | ||
| + | for(int k=n;k>=w[j];k--) temp_dp[k]=(temp_dp[k]+temp_dp[k-w[j]])%mod; | ||
| + | } | ||
| + | } | ||
| + | int q; | ||
| + | scanf("%d",&q); | ||
| + | while(q--){ | ||
| + | int x,y; | ||
| + | scanf("%d%d",&x,&y); | ||
| + | int l=conv(s[x-1]); | ||
| + | int r=conv(s[y-1]); | ||
| + | printf("%lld\n",W*ans[l][r]%mod); | ||
| + | } | ||
| + | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/lgwza/可逆背包.1626419575.txt.gz · 最后更改: 2021/07/16 15:12 由 lgwza
