2020-2021:teams:legal_string:lgwza:可逆背包
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:lgwza:可逆背包 [2021/07/16 22:57] lgwza |
2020-2021:teams:legal_string:lgwza:可逆背包 [2021/07/16 22:58] (当前版本) lgwza |
||
|---|---|---|---|
| 行 88: | 行 88: | ||
| - 现考虑 $(i,j)$ 的限制，即字母 $s[i]$ 和 $s[j]$ 需在同一组中，等价于去掉字母 $s[i]$ 和 $s[j]$ 的 01 背包问题，即作了一次 01 背包问题后，再枚举 $i,j$ 做退背包过程，将去掉 $(i,j)$ 的 DP 值记作 $ans[i][j]$； | - 现考虑 $(i,j)$ 的限制，即字母 $s[i]$ 和 $s[j]$ 需在同一组中，等价于去掉字母 $s[i]$ 和 $s[j]$ 的 01 背包问题，即作了一次 01 背包问题后，再枚举 $i,j$ 做退背包过程，将去掉 $(i,j)$ 的 DP 值记作 $ans[i][j]$； | ||
| - 最后对每个询问直接 $O(1)$ 输出答案即可。 | - 最后对每个询问直接 $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> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/lgwza/可逆背包.1626447468.txt.gz · 最后更改: 2021/07/16 22:57 由 lgwza
