考虑倍增。

$f(i,k), g(i,k)$ 分别表示从 $i$ 出发，走 $2^k$ 步经过的边权最小值和边权和。一开始 $f(i,0)=g(i, 0)=w_i$。

为了方便处理，我们定义 $to(i, k)$ 表示从 $i$ 出发，走 $2^k$ 步走到的点。$to(i, k)$ 显然是容易处理的。根据 $to(i, k)$ 预处理 $f(i, k), g(i, k)$ 即可。

时间复杂度 $O(n \log ⁡k )$。

题目名是一首歌。

最大值最小化，考虑二分答案，转向判断是否存在一条 $1\to n$ 的路径满足权值 $\le mid$。

我们考虑二分答案其实是给每条边加了一个限制，也就是权值为 $w_i$ 的边最晚在 $\lfloor \frac{mid}{w_i} \rfloor$ 时经过。之后不再合法。

我们考虑路径的形态，从而帮助我们理解这个问题。我们知道，如果 $1\to 2$ 和 $1\to 3\to 2$ 同时合法，那么我们一定会选择 $1\to 2$ 这条路径。

显然在合法的前提下，我们会尽可能地走最短路。这其实是一个贪心的思想。可以理解为，走最短路可以达到更多的后继状态，所以一定优于不走最短路。

于是变成了一个边权为 1 的最短路问题，bfs 求解即可。时间复杂度 $\mathcal O(n\log w)$。

这题有着高达 80 的 dp 部分分，并不是很理解为什么场上没有人打。

//这是我提交AC的第一道题

//庆祝一下写一篇题解~有什么不对欢迎提出

//一道经典的kmp题，一定要记住模版

//每一次询问时间复杂度大约O(n)的，使用O2评测机不会超时的哦

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#include<deque>
#include<list>
#include<stack>
#include<utility>
#define MAXN 1919810
#define ite iterator
#define fs fixed<<setprecision
typedef long long ll;
using namespace std;

inline ll read(){ll x=0,f=1;char z;z=getchar();while(z<'0'||z>'9'){if(z=='-')f=-1;z=getchar();}while(z>='0'&&z<='9')x=x*10+z-'0',z=getchar();return x*f;}
inline void write(ll x){if(x<0){x=-x;putchar('-');}if(x>9){write(x/10);}putchar(x%10+'0');}
//快读，快写，利用getchar()与putchar()比cin，cout快的特性
char p1 , p2;
int l1 , l2;
char str1[MAXN] , str2[MAXN];
int k[MAXN*2];

inline int solve(){
	memset(k , 0 , sizeof(k));//初始化数组
	int ans = 0;//答案
	register int x = 0;//以下是kmp的模版，比常规暴力时间更少
	for(register int i = 2 ; str2[i] ; ++i){
		while(x && str2[x+1] != str2[i])
			x = k[x];
		if(str2[x+1] == str2[i])
			++x;
		k[i] = x;
	}
	x = 0;
	for(register int i = 1 ; str1[i] ; ++i){
		while(x>0 && str2[x+1] != str1[i]){
			x = k[x];
		}
		if(str2[x+1] == str1[i]){
		}
		if(x == strlen(str2+1)){
			ans++;
			x = k[x];
		}
	}
	return ans;
}



int main(){
	
	freopen("oulipo.in" , "r" , stdin);
	freopen("oulipo.out" , "w" , stdout); 
	int n;
	n = read();
	//常规输入
	for(register int i = 1 ; i <= n ; ++i){
		memset(str1 , 0 , sizeof(str1));
		memset(str2 , 0 , sizeof(str2));
		scanf("%s" , str2+1);//下标从一开始
		scanf("%s" , str1+1);//格式化输入输出一定要学会。不喜欢的可以用cin更方便
		write(solve());
		putchar('\n');
	}
	
	return 0;
}

祝大家能顺利的通过每一场比赛！早日夺得noi金牌！加油！

跟下面那道题比起来属于是纯纯的小清新题了，这就是原友出题人和原批出题人的差距。不过当时的 FFT 应该没有现在这么普及，就像原神在最初几年也没有引起轩然大波一样。

这种组合数取模肯定考虑卢卡斯定理，况且 $n \lt p^{10}$ 也算是提醒你了。

将 $n$ 和 $k$ 写成 $p$ 进制数 $\overline{n_N...n_0}$ 和 $\overline{k_N...k_0}$，根据卢卡斯定理有 $C_n^k=\prod_i{C_{n_i}^{k_i}}$。显然每个 $k_i$ 的贡献是可以分开算的。

令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=j$ 的方案数，$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = j$ 的 $k$ 的数量，转移是简单的：

$$f_{i,j}=\sum_{(x\times y) \%p=j}{f_{i-1,x} g_{i,y}}$$

这转移式和卷积的相似度可以与原神媲美了，然而这个下标是相乘而不是相加。

但这玩意属于是典中典了，直接把下标对 $p$ 的原根取对数就可以转化成相加了，具体见 “[SDOI2015]序列统计”。

重新定义一下，令当前选择的原根是 $G$。

令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=G^j$ 的方案数，$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = G^j$ 的 $k$ 的数量，将转移写成和卷积：

$$F_i=\sum_{j\ge 0}{f_{i,j}x^j}\quad\quad G_i=\sum_{j\ge 0}{g_{i,j}x^j}$$

$$\Rightarrow F_{i}=\sum_{j\ge 0}(\sum_{(x+y)\%(p-1)=j}{f_{i-1,x} g_{i,y}})x^j=F_{i-1}G_i$$

大概就是这样，注意下标相加实际是指数相加，所以根据费马小定理对 $p-1$ 取模。以及这样卷积出来会有下标大于 $p-1$ 的项，及时合并到前面即可。

介于答案模数较小，使用 FFT 计算卷积，时间复杂度大概是 $O(10p\log(p))$。

勉强加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。

数个月前说要写，鸽到现在，菜。

属于是惊世骇俗的神秘题了。

拿到式子直接开始乱推:

$$ \sum_{i=1}^{n}{\gcd(i,n)^x \mathrm{lcm}(i,n)^y}\\ $$

$$   =\sum_{i=1}^{n}{i^yn^y\gcd(i,n)^{x-y}}\\ $$

$$   =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{n}{i^y[\gcd(i,n)=d]}}\\ $$

$$   =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{\frac{n}{d}}{(id)^y[\gcd(i,\frac{n}{d})=1]}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{i=1}^{\frac{n}{d}}{i^y\sum_{k|i,k|\frac{n}{d}}{\mu(k)}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)\sum_{i=1}^{\frac{n}{dk}}{(ik)^y}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=1}^{\frac{n}{dk}}{i^y}}}\\ $$

$$   =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^yS(\frac{n}{dk},y)}}\\ $$

玩原神的人都知道 $S(\frac{n}{dk},y)$ 是个 $y+1$ 次多项式，这就是原神带给我骄傲的资本。记 $S=\sum_{i=0}^{y+1}{f_ix^i}$ 代入：

$$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=0}^{y+1}{f_i(\frac{n}{dk})^i}}}\\$$

$$  =n^y\sum_{i=0}^{y+1}{f_i\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y{(\frac{n}{dk})^i}}}}\\$$

$$  =n^y\sum_{i=0}^{y+1}{f_i(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(n)}}\\$$

三个函数卷积，纯纯的卷狗。

好在三个积性函数卷出来也是积性函数，于是 pollard_rho 出 $n$ 的所有质因子分开算。

$$(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(p^c)}\\$$

$$  =\sum_{j=0}^{c}{\mu(p^j)p^{yj}\sum_{k=0}^{c-j}{p^{kx}p^{(c-j-k)i}}}\\$$

$$  =\sum_{k=0}^{c}{p^{ci+(x-i)k}}-p^y\sum_{k=0}^{c-1}{p^{(c-1)i+(x-i)k}}\\$$

两坨都是等比数列求和，好好好，玩原神玩的。

最后就是这个 $f_i$。

如果你玩原神，那么你就会伯努利数，那么就知道：

$$\sum_{i=1}^{n}{i^k}=\frac{1}{k+1}\sum_{j=0}^{k}{(-1)^jC_{k+1}^jB_jn^{k+1-j}}$$

其中 $B_j$ 是伯努利数，可以用 EGF 求：

$$B(x)=\sum_{i \ge 0}{B_i\frac{x^i}{i!}}=\frac{x}{e^x-1}$$

然后就结束了。原神，启动！

听说还很卡常，已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。

view in my cnblogs.

两年前的我这么强吗，还会写 30pts，现在的我 30pts 都写不出来。这种字符串工业太可怕了！

好吧，其实做法的提示性很强，这个东西明摆着是让你根号分治的。难点在于维护而不在于贪心。

我先口胡一个东西看看对不对啊。跑 SA，设阈值是 $B$，然后 $\gt B$ 的直接二分出来 $\rm sa$ 范围，然后扔主席树上不停进行区间查询时间复杂度是 $\mathcal O(\frac{nq}{B}\log n)$ 的一个东西。然后 $\le B$ 的子串只有 $\Theta(nB)$ 个。怎么预处理来着？

哦好像题目里规定了 $\le B$ 的很少，$r-l$ 随机均匀这个性质咋用？是想告诉我默认 $\tilde O(r-l)=1000$ 吗？

那我是不是还是可以和上面那个东西一样暴力跑啊 /qd。

看一眼 myee 的题解，好像还真行，$X=50,Y=2000$ 的话这个东西的复杂度就是

$$\mathcal O(\frac{\log n}{Y-X}\int_X^Y \frac{n}{x}\, \mathrm d x) = \mathcal O(n\log n\frac{\ln Y - \ln X}{Y-X})$$

我不会微积分啊，这个式子是抄的。写完这个一定要学一学微积分，要不然这种细致复杂度分析不会做 /ng。（学不会，开摆）

好像还有 $r-l\le X$ 的情况，这个咋办来着。

一般来说字符串这种东西可以反着来，想一想出题人会怎么卡。他要卡我的话肯定能匹配的越多越好，那这样的话询问的本质不同串是不是不会多。

看题解。好吧，首先按上面的方法找到第一个位置，然后倍增预处理就行。不想写代码，啥时候闲的蛋疼了再写。