内置了一些与各种乱七八糟知识点相关的题目。

一. 矩阵加速:

T1: Count

题意: 对于 f[n] = f[n-1] + 2 * f[n-2] + n^3,求其加速矩阵。

分析: 我们可以把后面那个讨厌的 n3n^3 用二项式定理展开成:

(n1+1)3=i=03(i3)(n1)i(n-1+1)^3 = \sum_{i=0}^3 \binom{i}{3}\cdot (n-1)^i

由于每一次幂都是线性无关的,于是乎构造一个转移 n3n^3 的矩阵(称其为 A),再和我们熟知的矩阵合并即可。

具体来讲,

[(n1)3(n1)2n10][1331012100110001]=[n3n2n0]\begin{bmatrix}(n-1)^3 \\(n-1)^2 \\n-1 \\0 \end{bmatrix}\cdot \begin{bmatrix} 1& 3& 3 & 1\\ 0& 1& 2& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1 \end{bmatrix} = \begin{bmatrix}n^3 \\n^2 \\n \\0 \end{bmatrix}

T2: Fibo 平方和

题意: 对于斐波拉契数列(n=109)(n=10^9),求其平方和取模后的值。

分析: 斐波拉契用矩阵加速好求,但平方项其实也能矩阵加速。由于 SnSn1=(fn)2=(fn1)2+2fn1fn2+(fn2)2S_n-S_{n-1} = (f_n)^2=(f_{n-1})^2+2 f_{n-1}f_{n-2}+(f_{n-2})^2
我们其实只需要维护SnS_n(fn)2(f_n)^2(fn1)2(f_{n-1})^2fnfn1f_n f_{n-1} 的项就行了,最后一项可以拆开。

二. 差分约束

T1:最小覆盖区间

题意: 给你 n 个要求 a_i ~ b_i 至少有 c_i 个数,让你找最小的一个集合满足这些要求。

分析:fif_i 表示 前 i 个数内至少有 fif_i 个才能满足条件,即得以下不等式限制条件:

{fbifai1cififi10fifi11\begin{cases} f_{b_i} - f_{a_i-1} \geq c_i\\ f_{i} - f_{i-1} \geq 0 \\ f_{i} - f_{i-1} \leq 1 \end{cases}

最后两个式子是暗含在定义内的,用差分约束也应该把它们带上。而且建边时应按照 vuwv-u\geq w 的逻辑(小者向大者建边),由 u 到 v 建一个长为 w 的边,对于该题即为: add(a_i-1, b_i, c_i), add(i-1, i, 0), add(i, i-1, -1)

如果跑 spfa 出了负环就是无解, 终点不可达即为任意(无穷)解。

三. 生成函数

转隔壁 多项式全家桶

四. 数位 DP

对于与数位有关的、范围较大的题目,可以套路性地用数位 DP 求解。我们利用低数位总是会重复的性质(如 1~9400 中,至少有八次你会枚举 0~9999),因此数位 DP 的第一维通常是 满 i 位时所有数的贡献,之后再根据不同的条件进行限制、转移。

T1 : 恨七不成妻

题意:

求在一定区间内和7无关的数字的平方和。一个数与 7 有关当且仅当:

1、整数中某一位是7;
2、整数的每一位加起来的和是7的整数倍;
3、这个整数是7的整数倍;

分析:

考虑对于任意 x,求出 1~x 所有与 7 无关的数的平方和,答案转化为前缀和的形式;对于题目要求的条件,我们还应该维护每一位加起来该数本身对于 7 的模数。

综上,我们设 f[i,f1,f2] 为当前是满 i 位,且上述的两个条件模数为 f1,f2 时的平方和。当一个数从高位向低位转移计算平方和的时候,我们将其拆成两部分(最高位及低位),递归地计算并合并。

利用平方和公式求解时,发现还需维护:满 i 位时与 7 无关的数的个数以及和

代码:


const int p = 1e9+7;
ll n, m, num[21], pw[21]; //囊括所有影响状态的变量
struct ans{
ll nm, sm, sm1;
ans() { nm = sm = sm1 = 0;}
ans(ll nm,ll sm,ll sm1) : nm(nm), sm(sm), sm1(sm1) {}
}f[21][10][10];

ans dfs(int k, int f1, int f2, bool is_max)
// f1 -> 数位和膜 7,f2 -> 整数膜 7
{
if (!k) return (f1 && f2 ? ans(1,0,0) : ans(0,0,0));
if (!is_max && f[k][f1][f2].nm) return f[k][f1][f2];
int mx = is_max ? num[k] : 9; ans sum, now;
for (int i=0;i<=mx;i++) {
if (i==7) continue;
now = dfs(k-1, (i+f1)%7, (f2*10+i)%7, is_max && i==mx);
ll hi = i*pw[k-1] %p, hi2 = hi*hi%p;
sum.nm = (sum.nm + now.nm) %p,
sum.sm = (sum.sm + now.nm*hi %p + now.sm %p) %p,
sum.sm1 = (sum.sm1 + now.nm*hi2 %p + 2*hi*now.sm %p + now.sm1 %p) %p;
}
if (!is_max) f[k][f1][f2] = sum; return sum;
}

ll solve(ll x)
{
int p=0;
while (x) num[++p] = x%10, x /= 10;
ans t = dfs(p, 0, 0, 1);
return t.sm1;
}

int main()
{
pw[0] = 1; for (int i=1;i<=20;i++) pw[i] = pw[i-1] * 10 %p;
int t; cin >>t;
while (t--) {
cin >> n >> m;
if (!n && !m) return 0;
cout << (solve(m) - solve(n-1) + p)%p << endl;
}
return 0;
}

五. 二分答案

题意:

给定两个大小为 10510^5 的序列,求两序列交叉乘积的第 k 小。

分析:

二分答案 mid,check 函数判断 两序列交叉乘积有多少个小于 mid 即可。
将两个序列排序后,我们只需要将一号指针 p1 指向序列 1 的头,二号指针 p2 指向序列 2 的尾,依次判断当前数是否满足条件即可。

由单调性,当 a[p1]*b[p2] > k 时,a[p1+1]*b[p2] > k 必然成立,因此整个时间复杂度是 O(n) 的。

代码:

bool check(ll x)
{
ll cnt = 0, j = m;
for (int i=1;i<=n;i++) {
while (j && a[i]+b[j]>=x) j--;
cnt += j; //单调性,用尺取法计算小于 x 的对数
}
return (cnt < k);
}

六. 单调队列

题意:

给定一个长度为nn的序列a1,a2,,ana_1,a_2,…,a_n和一个参数mm (1n100000,1m109)(1\leq n\leq 100000,1\leq m\leq 10^9)

  • 你要从中删掉若干个位置p1,p2,,pkp1,p_2,…,p_k (1p1<p2<<pkn)(1\leq p_1<p_2<…<p_k\leq n),耗费i=1ki×api\sum_{i=1}^k i\times a_{p_i}的代价。

  • 上一步会把序列分割成k+1k+1段,对于剩下的每段求和,如果某一段的和sum>msum>m,则要额外支付 sumsum 的代价。

求最小总代价。

分析:

最暴力的做法是设 f[i][j] 表示前i个位置一共删除 j 个位置的最小代价,且第 i 个位置必被删。此时得到转移方程:

fi,j=maxk=1i1{ fk,j1+(sum>m?sum:0) }+jaif_{i,j} = \max_{k=1}^{i-1} \left \{ ~f_{k,j-1} + (sum>m ? sum : 0)~\right \} + j*a_i

但这个是 O(n3)O(n^3) 的,考虑优化。对于 sum=s[i1]s[k]sum = s[i-1] - s[k] 有两种可能,若 sum>msum > m 则收费,代价是 min(fk,j1sk)\min (f_{k,j-1} -s_k),可以直接维护前缀最小值;若 summsum \le m 则不用收费,代价 minfk,j1\min f_{k,j-1}。由于前缀和数组 s 递增,那么一定存在一个分界线,使得之前情况都是前者、而之后的情况都是后者;又由于 m 固定,这个分界线随着 i 的增加一定是增大的,因此可以用 单调队列 维护。

k 可以任选,但由于 aia_i10310^3 量级,经测试 k 不会大于 200.

代码:

#include <bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define ok cout<<'!'<<endl
#define inf 2147483647
#define ll long long
#define fir first
#define sec second
#define pr pair<int,ll>
using namespace std;

ll read()
{ ll x=0,f=0; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}

const int maxn = 1e5+10;
ll n, m, a[maxn], s[maxn], f[2][maxn], *f0, *f1;
deque<pr> q;

inline void q_clear() { q.clear(), q.push_back(make_pair(0, 0)); }
int main()
{
int T = read();
while (T--) {
ll ans = inf/2; n = read(), m = read();
for (int i=1;i<=n;i++) a[i] = read(), s[i] = s[i-1] + a[i];
memset(f, 0x3f, sizeof(f));
f0 = f[0], f1 =f[1], a[++n] = 0, s[n] = s[n-1];
f0[0] = f1[0] = 0, q.push_back(make_pair(0, 0));

for (int k=1;k<=2*sqrt(n);k++) {
ll p = 0, tmp = inf/2; // p 为分界线指针
for (int i=1;i<=n;i++) {
while (s[i-1]-s[p] > m)
tmp = min(tmp, f0[p]-s[p]), p++;
f1[i] = tmp + s[i-1];
while (!q.empty() && q.front().fir < p) q.pop_front();
f1[i] = min(f1[i], q.front().sec) + a[i] * k;
while (!q.empty() && q.back().sec >= f0[i]) q.pop_back();
q.push_back(make_pair(i, f0[i])); // 用 f[i-1] 调整单调队列
}
ans = min(ans, f1[n]);
swap(f0, f1), q_clear();
}
printf("%lld\n", ans);
}
return 0;
}