首页 > 其他分享 >题解 CF1780G【Delicious Dessert】

题解 CF1780G【Delicious Dessert】

时间:2023-01-26 10:00:12浏览次数:66  
标签:__ SAM int 题解 CF1780G Delicious Dessert operatorname

SAM 板子题。

P3804 【模板】后缀自动机 (SAM) 中,我们已经会求每个等价类(SAM 状态)在原串中的出现次数。

本题中,我们需要求所有长度能被出现次数整除的子串。我们知道一个等价类中的所有字符串的长度构成一段整数区间 \([\operatorname{minlen}(v),\operatorname{maxlen}(v)]\),其中 \(\operatorname{minlen}(v)=\operatorname{maxlen}(\operatorname{link}(v))\)。于是想到将每个整数的因数打表到 vector 中,然后二分即可统计这一等价类中有多少子串符合条件。

复杂度 \(\mathcal O(n\log n)\)。

// Problem: CF1780G Delicious Dessert
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1780G
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e6+5;

char s[N];
int n, dp[N<<1]; ll ans;
vector<int> divisors[N], e[N<<1];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct State {
	int len, link, nxt[26];
};
struct SAM {
	State st[N<<1];
	int sz, lst;
	void init() {
		st[0].len = 0;
		st[0].link = -1;
		sz = lst = 0;
	}
	void extend(char ch) {
		int u = ++sz, c = ch - 'a';
		st[u].len = st[lst].len + 1;
		int p = lst;
		for(;p!=-1&&!st[p].nxt[c];p=st[p].link) st[p].nxt[c] = u;
		if(p == -1) st[u].link = 0;
		else {
			int q = st[p].nxt[c];
			if(st[p].len + 1 == st[q].len) st[u].link = q;
			else {
				int v = ++sz;
				st[v].len = st[p].len + 1;
				st[v].link = st[q].link;
				memcpy(st[v].nxt, st[q].nxt, sizeof(st[q].nxt));
				for(;p!=-1&&st[p].nxt[c]==q;p=st[p].link) st[p].nxt[c] = v;
				st[q].link = st[u].link = v;
			}
		}
		lst = u;
		dp[u] = 1;
	}
}sam;
int calc(int c, int x) {
	return upper_bound(divisors[c].begin(), divisors[c].end(), x) - divisors[c].begin();
}
void dfs(int u) {
	for(auto v : e[u]) {
		dfs(v);
		dp[u] += dp[v];
	}
	if(!u) return;
	int cnt = calc(dp[u], sam.st[u].len) - calc(dp[u], sam.st[sam.st[u].link].len);
	ans += 1LL * cnt * dp[u];
}

int main() {
	scanf("%d%s", &n, s+1);
	rep(i, 1, n) for(int j = i; j <= n; j += i) divisors[j].push_back(i);
	sam.init();
	rep(i, 1, n) sam.extend(s[i]);
	rep(i, 1, sam.sz) e[sam.st[i].link].push_back(i);
	dfs(0);
	printf("%lld\n", ans);
	return 0;
}

标签:__,SAM,int,题解,CF1780G,Delicious,Dessert,operatorname
From: https://www.cnblogs.com/ruierqwq/p/CF-1780G.html

相关文章

  • CF850F 题解
    题意传送门有一袋\(n\)个颜色球,第\(i\)个颜色的球有\(a_i\)个。当袋子里至少有两个不同颜色的球时,执行以下步骤:一个接一个的按照顺序随机取出两个的球,这些球......
  • 安装OpenCV时提示缺少boostdesc_bgm.i文件的问题解决方案
    安装OpenCV时,会遇到下面的错误/home/zhang/slam/opencv-3.4.5/opencv_contrib/modules/xfeatures2d/src/boostdesc.cpp:653:20:fatalerror:boostdesc_bgm.i:没有那个文......
  • LeetCode-343. 整数拆分 - 题解分析
    题目来源343.整数拆分题目详情给定一个正整数 n ,将其拆分为k个正整数的和( k>=2 ),并使这些整数的乘积最大化。返回你可以获得的最大乘积 。示例1:输入:......
  • 题解 CF1773H【Hot and Cold】
    赛时跟队友一起摆烂了,于是没做出来,回来补题。如果询问到了答案,可以直接判断并退出,因此下文的询问过程并没有考虑这一点。显然“\((1,1)\)比\((0,0)\)离所求位置更近”......
  • 关于gnome-control-center的问题解决
    突然发现电脑桌面的设置无法打开,点击后一直转圈。在网上研究了一圈,发现可能是gnome出了问题,输入指令gnome-control-center,结果报了如下错误:gnome-control-center:......
  • 洛谷 P1478 陶陶摘苹果(升级版) 题解
    这道题只要会自定义cmp恰当地进行排序,其他部分没有什么大问题。上代码:1#include<bits/stdc++.h>2usingnamespacestd;3intn,s,h1,h2,cnt;4structapple{......
  • CF Educational Round 142 (Rated for div2) 题解
    A注意到除了血量为\(1\)的怪物,其余的怪物直接斩杀是更合理的。所以只要统计血量为\(1\)的怪物的个数即可。#include<cstdio>voidsolve(){ intn;scanf("%d",......
  • 洛谷 P1094纪念品分组 题解
    一道典型的贪心算法题。题目内容不多说了,大致说一下代码的思路:给定的所有纪念品中可以先用sort排一下顺序,然后从价格最高和最低的开始向中间靠拢(可以看做是指针),这样保证......
  • 洛谷 P2440木材加工 题解
    这是一道二分答案算法题,洛谷标签中的贪心等完全用不到。这道题的数据范围较大,所以保险起见,整型的数据我们都开成longlong题意很好理解,这里就不做过多的分析了,直接看代码......
  • 洛谷P1259 黑白棋子的移动 题解
    本蒟蒻这题用的打表做法,其实也可以理解为是一种递推。先来观察一下样例:当n为7时,输出共有14行,易得输出行数为2n。ooooooo*******--oooooo--******o*oooooo******--o......