7.2-
每 \(10\) 题一篇 \(\texttt{>o<}\) 。
7-1 1845E. AND Graph
\(\texttt{Difficulty:UnKnown}\)
题意
\(n(1\le n\le1500)\) 个 \(1\) 的 \(01\) 序列，每次可以将一个 \(1\) 挪到相邻的 \(0\) 上去，求恰好 \(k(1\le k\le1500)\) 次操作后，能有多少种不同的 \(01\) 序列。
题解
下设 \(n,k\) 同阶。
考虑无论如何操作最开始的 \(1\) 的相对次序都不会发生改变，记最开始每个 \(1\) 的位置为 \(a_i\) ，操作后的为 \(b_i\) ，于是最小操作步数为 \(\sum|b_i-a_i|\) ，如果一个方案的最小步数与 \(k\) 奇偶性相同，那么就是合法的方案，因为可以让一个 \(1\) 反复横跳来达到恰好 \(k\) 步。
一个比较容易想到的 \(\texttt{DP}\) 方法是记 \(f_{i,j,k}\) 表示前 \(i\) 个位置，放了 \(j\) 个 \(1\) ，最少步数为 \(k\) 的方案数，每次分情况放 \(1\) 与不放 \(1\) 向后转移，复杂度为 \(\mathcal{O}(n^3)\) ，考虑进一步优化。
考虑分别记 \(A_i,B_i\) 为操作前后 \(01\) 序列的前缀和， \(d_i\) 为前缀和的差值 \(B_i-A_i\) ，对于最小步数，我们可以统计每个 \(i\sim i+1\) 的区间的贡献来计算，即对于每个 \(d_i\) ，表示会有 \(|d_i|\) 个 \(1\) 在操作时需要通过 \(i\sim i+1\) 区间，于是最小步数为 \(\sum|d_i|\) 。因为总步数不能超过 \(k\) 的限制，而相邻两个 \(|d_i\) 至多差 \(1\) ，考虑 \(\sum|d_i|\) 的最小值即 \(\frac{(1+d_i)d_i}{2}\le k\) ，因此必然有 \(|d_i|\le\mathcal{O}(\sqrt k)\) ，于是可以把原来 \(\texttt{DP}\) 的第二维改为当前的 \(d_i\) 为 \(j\) ，这样第二维只用枚举至多 \(\mathcal{O}(\sqrt k)\) 个状态，于是复杂度 \(\mathcal{O}(n\sqrt n)\) 。
代码
view code
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<LL, LL>;
using TP = tuple<int, int, int>;
#define all(x) x.begin(),x.end()
#define mst(x,v) memset(x,v,sizeof(x))
#define mul(x,y) (1ll*(x)*(y)%mod)
#define mk make_pair
//#define int LL
//#define double LD
#define lc p*2
#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const double pi = acos(-1);
const LL mod = 1000000007;
//const LL mod = 998244353;
const int maxn = 1510;
LL N, K, A[maxn], f[2][130][maxn], h = 60;
void solve()
{
f[0][h][0] = 1;
for (int i = 1; i <= N; i++)
A[i] += A[i - 1];
for (int i = 1; i <= N; i++)
{
for (int j = -60; j <= 60; j++)
{
for (int k = 0; k <= K; k++)
{
f[i % 2][j + h][k] = 0;
LL tj = j - (A[i - 1] - A[i]);
if (k - abs(j) >= 0)
{
f[i % 2][j + h][k] = (f[i % 2][j + h][k] + f[(i - 1) % 2][tj + h][k - abs(j)]) % mod;
f[i % 2][j + h][k] = (f[i % 2][j + h][k] + f[(i - 1) % 2][tj - 1 + h][k - abs(j)]) % mod;
}
}
}
}
LL sum = 0;
for (int i = 0; i <= K; i++)
{
if ((K - i) % 2 == 0)
sum = (sum + f[N % 2][h][i]) % mod;
}
cout << sum << endl;
}
int main()
{
IOS, cin >> N >> K;
for (int i = 1; i <= N; i++)
cin >> A[i];
solve();
return 0;
}