题意
问\(S\)个数，使得\(S\)与\(S_1,S_2,S_3\)的距离满足上限。
思路
正难则反，转化为相等位满足上限。
\(O(n^2)\)肯定要枚举些什么？
发现\(0/1\)大小关系状态有限。
把每列根据第\(2\)和\(3\)个跟第\(1\)个的大小关系分为四类。
令第\(i\)类列数为\(k_i\)，\(t_i\)第\(i\)种情况\(S=S_1\)的列数。
答案当然就是 \(\sum\limits_{t1} \sum\limits_{t2} \sum\limits_{t3} \sum\limits_{t4} \binom{k1}{t1} \binom{k2}{t2} \binom{k3}{t3} \binom{k4}{t4}\)
\(O(n^4)\) 直接枚举 \(t_i\) ，可以平衡规划一下，只枚举 \(t3\) 和 \(t4\) ，然后就有关于 \(t1+t2\le R\) 和 \(t1+k2-t2\le R'\) 两个限制，二维数点，其实把每一对 \((t1,t2)\) 更入 \((t1+t2,t1+k2-t2)\) 中，求一下二维前缀和即可。
code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
const int mod = 1e9 + 7;
char s1[N], s2[N], s3[N];
int n, r1, r2, r3, k1, k2, k3, k4;
int ans, F[N][N], C[N][N];
int main() {
scanf("%d", &n);
scanf("%d", &r1); scanf("%s", s1 + 1); r1 = n - 1 - r1;
scanf("%d", &r2); scanf("%s", s2 + 1); r2 = n - 1 - r2;
scanf("%d", &r3); scanf("%s", s3 + 1); r3 = n - 1 - r3;
for(int i = 0; i <= n; i++) {
C[i][0] = 1; for(int j = 1; j <= i; j++) {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}
}
ll pw2 = 1;
for(int i = 1; i <= n; i++) {
pw2 = pw2 * 2 % mod;
bool f1 = (s2[i] == s1[i]), f2 = (s3[i] == s1[i]);
if(f1 && f2) {k1++;}
else if(f1 && !f2) {k2++;}
else if(!f1 && f2) {k3++;}
else {k4++;}
}
for(int t1 = 0; t1 <= k1; t1++) {
for(int t2 = 0; t2 <= k2; t2++) {
ll w = 1ll * C[k1][t1] * C[k2][t2] % mod;
F[t1 + t2][t1 + k2 - t2] = (F[t1 + t2][t1 + k2 - t2] + w) % mod;
}
}
for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) F[i][j] = (F[i][j] + F[i - 1][j]) % mod;
for(int i = 0; i <= n; i++) for(int j = 1; j <= n; j++) F[i][j] = (F[i][j] + F[i][j - 1]) % mod;
ll ans = pw2;
for(int t3 = 0; t3 <= k3; t3++) {
int t3_ = k3 - t3;
for(int t4 = 0; t4 <= k4; t4++) {
int t4_ = k4 - t4, lim1 = min(r1 - t3 - t4, r2 - (t3_ + t4_)), lim2 = r3 - (t3 + t4_);
if(lim1 < 0 || lim2 < 0) continue;
ans = (ans - 1ll * C[k3][t3] * C[k4][t4] % mod * F[lim1][lim2]) % mod;
}
}
printf("%lld", (ans + mod) % mod);
return 0;
}