• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# CF1111D Destroy the Colony

7小时前 2次浏览

## CF1111D Destroy the Colony

(ans = frac{n!}{r1!r2!….rn!})

(m = frac{n}{2}),我们知道一种拼凑方式的排列答案为frac{m!}{(a1!….an!)} * frac{m!}{(b1!….bn!)}

``````// Problem: CF1111D Destroy the Colony
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1111D
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 100010
#define mod 1000000007
#define QWQ QAQ

ll a[N],f[N],fac[N],inv[N],mul;
ll n,m,q,cnt[53],ans[53][53];
char ch[N];

int char_to_int(char x) {
if(x >= 'a' && x <= 'z') return x-'a';
return x-'A'+26;
}

inline ll pow(ll a,ll b){
ll ans = 1;
while(b){
if(b & 1)ans = a * ans % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}

if(x == 0)return ;
for(int i = m;i >= x;--i)f[i] = (f[i] + f[i - x] > mod ? f[i] + f[i - x] - mod : f[i] + f[i - x]);
}

inline void del(int x){
if(x == 0)return;
for(int i = x;i <= m;++i)f[i] = (f[i] - f[i - x] + mod > mod ? f[i] - f[i - x] : f[i] - f[i - x] + mod);
}

ll ans = 0;
char a = getchar();
while(!(a <= '9' && a >= '0'))
a = getchar();
while(a <= '9' && a >= '0')
ans = (ans << 3) + (ans << 1) + (a - '0'),a = getchar();
return ans;
}

int main(){
scanf("%s",ch + 1);
n = std::strlen(ch + 1);
m = n / 2;
fac[0] = 1;
for(int i = 1;i <= n;++i)
fac[i] = fac[i - 1] * i % mod;
inv[n] = pow(fac[n],mod - 2);
mul = fac[m] * fac[m] % mod;
for(int i = n - 1;i >= 0;--i)
inv[i] = inv[i + 1] * (i + 1) % mod;
for(int i = 1;i <= n;++i)
a[i] = char_to_int(ch[i]),cnt[a[i]] ++ ;
f[0] = 1;
for(int i = 0;i < 52;++i){
mul = mul * inv[cnt[i]] % mod;
}
for(int i = 0;i < 52;++i)ans[i][i] = f[m];
for(int i = 0;i < 52;++i)
for(int j = i + 1;j < 52;++j){
del(cnt[i]),del(cnt[j]);
ans[i][j] = ans[j][i] = f[m];
del(cnt[i] + cnt[j]);