标签 - SPOJ

? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:19    786    0    0
传送门 题意:计算σ0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和 以前雅礼集训的时候就听说过这题,好像是洲阁筛板子? 但是如今世道不同了,Min_25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛! 当p∈Prime,f(pc)=3c+1" role="present
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:17    546    0    0
传送门 题意:计算σ0(ik)\sigma_0(i^k)的前缀和 一道牛逼题目,Min_25Min\_25筛写的很简短。 当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1 且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1 又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1) 直接Min_25Min\_25筛就行了,复杂度O(1011)O(10^{11})能过。 #include<cstdio>#include<algorithm>#
? 解题记录 ? ? SPOJ ? ? 原根 ?    2018-12-19 11:24:41    430    0    0
题目描述 给你一个质数p" role="presentation" style="position: relative;">ppp以及n" role="presentation" style="position: relative;">nnn组询问, 判定给定的r" role="presentation" style="position: relative;">rrr是否为p" role="presentation" style="position: relative;">ppp的原根。 输入输出格式 输入格式 题目有多组测试数据。 每组测试数据的第一行两
? 解题记录 ? ? SPOJ ? ? 后缀数组 ?    2018-12-05 23:04:22    441    0    0
后缀数组模板题,直接看注释就好了 #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int maxn = 1e5 + 5; char s[maxn]; LL ans; int SA[maxn], SA2[maxn], RK[maxn], tot[maxn], H[maxn]; //SA : 第一关键字排名为i的开头下标 //SA2 : 第二关键字排名为i的开头下标 //RK : 原字符串中下标为i后缀的
? 解题记录 ? ? SPOJ ? ? 后缀数组 ?    2017-12-09 16:09:16    350    0    0
Given a string, we need to find the total number of its distinct substrings. InputT- number of test cases. T<=20; Each test case consists of one string, whose length is <= 1000 OutputFor each test case output one number saying the number of distinct substrings. ExampleSample Input: 2 CCCCC ABA
? 解题记录 ? ? SPOJ ? ? 后缀自动机 ? ? 动态规划 ?    2017-10-01 12:59:43    411    0    0
A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string. Now your task is a bit harder, for some given strings, find the l
? 解题记录 ? ? SPOJ ? ? 后缀自动机 ? ? 补档计划第一期 ?    2017-08-31 20:19:13    516    0    0
LCS - Longest Common Substringno tags  A string is finite sequence of characters over a non-empty finite set Σ. In this problem, Σ is the set of lowercase letters. Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string. Now your task is si