洛谷P5982 [PA2019] Trzy kule 题解
题意:
对于两个长度为 \(n\) 的 \(01\) 串 \(a_{1..n},b_{1..n}\),定义它们的距离 \(d(a,b)=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\)。
给定三个长度为 \(n\)的 \(01\) 串 \(s_1,s_2,s_3\)以及三个非负整数 \(r_1,r_2,r_3(0\le r_i\le n)\),问有多少个长度为 \(n\) 的 \(01\) 串 \(S\)满足\(d(S,s_1)\le r_1,d(S,s_2)\le r_2,d(S,s_3)\le r_3\) 这三个不等式中至少有一个成立。
输入格式:
第一行一个正整数 \(n\)。
第二行一个非负整数 \(r_1\),然后一个长度为 \(n\) 的 \(01\) 串 \(s_1\)。
第三行一个非负整数 \(r_2\),然后一个长度为 \(n\) 的 \(01\) 串 \(s_2\)。
第四行一个非负整数 \(r_3\),然后一个长度为 \(n\) 的 \(01\) 串 \(s_3\)。
输出格式:
输出一行一个整数,即满足条件的 \(S\) 的数量模 \(10^9+7\)。
数据范围:
对于 \(100\%\) 的数据,\(1\le n\le 10^4\)。
条件计数的常见解法:要么容斥,要么寻找更简洁的充要条件。
这道题,其实两者都有所运用。
首先最基本的容斥,考虑计算不满足任何一个等式的串的个数,最后用 \(2^n\) 减去它就是答案。
方便起见,我们可以先把 \(s_1\) 变为 \(\mathtt{111\dots}\) (全为 \(\mathtt{1}\) ),并将 \(s_2\) 和 \(s_3\) 进行变换。
依次考虑每个位。由于我们的变换操作,现在这三个字符串在每位的情况只有
100,101,110,111
四种。
不妨记这四种情况分别有 \(a_1,a_2,a_3,a_4\) 种。
我们枚举因 \(S\) 导致的
110
和 111
的出现次数 \(i,j\) ,则 001
和
000
的出现次数就为 \(a_3 - i,~a_4
- j\) 。
此时对应 \(s_1\) 和对应 \(s_2\) 的串中出现的 \(\mathtt{1}\) 的个数是一样的,都是 \(i + j\) ,对应 \(s_3\) 的串中出现的为 $i + a_4 -j $
设 100
和 101
的出现次数分别为 \(x,y\) 。那么我们需要满足以下条件: \[
\begin{aligned}
& i+j+x+y>t_1
\\[6pt]& i+j+\left(a_1-x\right)+\left(a_2-y\right)>t_2
\\[6pt]& i+\left(a_4-j\right)+\left(a_1-x\right)+y>t_3
\end{aligned}
\] 整理并合并后可以得到以下不等式: \[
\begin{aligned}
&i+j>\max \left(t_1-x-y,
t_2-\left(a_1-x\right)-\left(a_2-y\right)\right)
\\[6pt]&i - j > t_3 - (a_1 - x) - y - a_4
\end{aligned}
\] 任意 \((i + j, i - j)\)
可以唯一确定一组 \(i,j\) 。
显然,可以和任何一组 \(x,y\) 产生贡献的 \(i,j\) ,其对应的 \((i + j, i - j)\) 都落在一个矩形区域内
那么算法就出来了。枚举 \(i,j\) ,其本身有 \(\binom{a_3}{i}\binom{a_4}{j}\) 种不同方案,我们把它加到二维平面上的点 \((i+j,i-j)\) 处
接着枚举 \(x,y\) ,其本身有 \(\binom{a_1}{x}\binom{a_2}{y}\) 种不同方案。接着我们只需统计矩形区域内的和,这一点可以通过预处理。
时间复杂度 \(\mathcal{O}(n^2)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))
char s1[N],s2[N],s3[N];
int n,t1,t2,t3,_111,_101,_100,_110,res,fac[N],inv[N],D[N][N];
int qpow(int a,int b)
{
int r = 1;
while(b) {
if(b & 1) r = r * a % mod;
b >>= 1; a = a * a % mod;
}
return r;
}
int C(int n, int m)
{
if(m < 0 || n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> t1 >> (s1 + 1) >> t2 >> (s2 + 1) >> t3 >> (s3 + 1);
for(int i = 1; i <= n; i++)
{
if(s1[i] == s2[i] && s2[i] == s3[i]) ++_111;
else if(s1[i] == s2[i]) ++_110;
else if(s1[i] == s3[i]) ++_101;
else ++_100;
}
if(_110 > _101) { swap(_110, _101), swap(t2, t3); }
if(_110 > _100) { swap(_110, _100), swap(t1, t3); }
fac[0] = 1;
for(int i = fac[0] = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for(int i = n - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
for(int i = 0; i <= _110; i++)
for(int j = 0; j <= _111; j++)
{
int A = i + j, B = j + _110 - i;
D[A][B] = (D[A][B] + C(_110, i) * C(_111, j)) % mod;
}
for(int i = _110 + _111; ~i; i--)
{
int *X = D[i], *Y = D[i + 1];
for(int j = _110 + _111 - max(i - _111, 0ll); ~j; j--)
X[j] = (X[j] + Y[j] + X[j + 1] - Y[j + 1] + mod) % mod;
}
for(int i = 0; i <= _100; i++)
for(int j = 0; j <= _101; j++)
{
int LA = max(t1 + 1 - i - j, t2 + 1 - (_100 - i) - (_101 - j));
int LB = t3 + 1 - (j + _100 - i); up(LA, 0); up(LB, 0);
res = (res + D[LA][LB] * C(_100, i) % mod * C(_101, j)) % mod;
}
res = ((qpow(2, n) - res) % mod + mod) % mod;
cout << res << '\n';
return 0;
}
参考文献: