[Sleeping Cup #8] D. Sorrowful Substrings - 题目

内存限制：512 MiB 时间限制：1000 ms 输入文件：sorrow.in 输出文件：sorrow.out

题目类型：传统评测方式：文本比较

上传者：匿名

提交提交记录统计测试数据讨论题解

注记：

本题中表示截取字符串的第个字符所得到的子串。

一个字符串被称为「23 串」，当且仅当不包含除和以外的任何字符。

同一序列的两个子序列和本质不同，当且仅当集合和不相等。请注意，这并不意味着序列和一定不相等。

本题中的值超过了 64 位有符号整数（以及 64 位无符号整数）的存储范围，建议使用 C++14（或更高版本）中引入的 __int128 扩展数据类型进行存储。请注意，不要使用 __int128 类型的变量（或常量）作为参数调用 cmath（math.h）库中的函数（如绝对值函数 abs，算术平方根函数 sqrt 等），否则可能会导致编译错误。

你可以使用以下代码（使用时需要包含 <cstdio> 或 <bits/stdc++.h> 头文件），并用 read() 读入一个 __int128 类型的正整数，用 readline() 读入一行一个 23 串（该函数返回一个 std::string 类型的字符串，使用时需要包含 <string> 或 <bits/stdc++.h> 头文件），用 writeline(x) 输出一行一个 __int128 类型的非负整数。请注意，不要将以下代码和其他输入输出方式混用：

inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
inline std::string readline()
{
	std::string x = "";
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x += c;
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}

对于一个长度为的非空 23 串，定义其权值为：

即中本质不同的子序列的个数。

定义一个非空 23 串是「不开心的」，当且仅当。

现给定一个长度为的 23 串，求中「不开心的」非空子串的数量。

第一行两个正整数。

第二行一个长度为的 23 串。

一行一个非负整数表示答案。

样例输入

20 16
32323232323232323232

样例输出

样例解释

「不开心的」非空子串有：

（共有个）
（共有个）
（共有个）
（共有个）
（共有个）
（共有个）
（共有个）
（共有个）
（共有个）

故答案为：

编辑器加载中 …

或者，上传代码文件

Powered by SYZOJ. Modified by Zemu (UnratedCheater).

项目源码 · 新ICP备2026003452号-2

当前版本：V1.7.1

#10083. [Sleeping Cup #8] D. Sorrowful Substrings

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

样例解释

显示分类标签