简要题意
给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：
- 长度不同时，长度短的排在低次位。
- 长度相同时，按字典序排序。
简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。
数据范围
\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)
Continue reading →给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：
简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。
\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)
Continue reading →思博题，没什么好讲的。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll n;
scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
}
return 0;
}
Continue reading → 有意思。之前做过一题是用矩阵树+高斯消元插值求本题的一维情况，本打算用继续这么做，后面发现 Lagrange 插值能做到 \(\Theta(n^5)\)，就学了一点新的东西。
首先，要认识到本题矩阵树出来之后可以得到一个二元多项式：
\[ \sum_{i = 0}^{n – 1} \sum_{j = 0}^{n – 1} a_{i, j} x^i y^j \]
Continue reading →如果你手上有一堆散点，然后你可以用这个公式拟合出一个函数：
\[ f(x) = \sum_{i = 1}^n y_i \prod_{j \neq i}^n \frac{x – x_j}{x_i – x_j} \]
Continue reading →