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

一. 矩阵加速：

T1: Count

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

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

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

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

具体来讲，

[(n−1)3(n−1)2n−10]⋅[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)，求其平方和取模后的值。

分析： 斐波拉契用矩阵加速好求，但平方项其实也能矩阵加速。由于 Sn−Sn−1=(fn)2=(fn−1)2+2fn−1fn−2+(fn−2)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、(fn−1)2(f_{n-1})^2、fnfn−1f_n f_{n-1} 的项就行了，最后一项可以拆开。

二. 差分约束

T1：最小覆盖区间

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

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

{fbi−fai−1≥cifi−fi−1≥0fi−fi−1≤1\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}

最后两个式子是暗含在定义内的，用差分约束也应该把它们带上。而且建边时应按照 v−u≥wv-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 (1≤n≤100000,1≤m≤109)(1\leq n\leq 100000,1\leq m\leq 10^9)。

  • 你要从中删掉若干个位置p1,p2,…,pkp1,p_2,…,p_k (1≤p1<p2<…<pk≤n)(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=max⁡k=1i−1{ fk,j−1+(sum>m?sum:0) }+j∗aif_{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[i−1]−s[k]sum = s[i-1] - s[k] 有两种可能，若 sum>msum > m 则收费，代价是 min⁡(fk,j−1−sk)\min (f_{k,j-1} -s_k)，可以直接维护前缀最小值；若 sum≤msum \le m 则不用收费，代价 min⁡fk,j−1\min f_{k,j-1}。由于前缀和数组 s 递增，那么一定存在一个分界线，使得之前情况都是前者、而之后的情况都是后者；又由于 m 固定，这个分界线随着 i 的增加一定是增大的，因此可以用 单调队列 维护。

k 可以任选，但由于 aia_i 在 10310^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;
}