CodeChef-PALSTR

题目描述

给定三个仅由小写英文字母组成的字符串 $A,B,C$。

你需要分别从三个串中选取一个非空连续子串 $S_A,S_B,S_C$，按顺序拼接成

$$ T=S_A+S_B+S_C. $$

请计算使 $T$ 为回文串的选取方案数，并返回方案数对 $998244353$ 取模的结果。

回文串是指从左往右读与从右往左读完全相同的字符串。两个方案不同，当且仅当至少一个所选子串的起点或终点不同；即使选出的字符串内容相同，只要位置不同，仍视为不同方案。

函数接口

这是一道 IOI 风格的函数式交互题。你只需提交一个 C++17 源文件，实现头文件 pld.h 中声明的函数：

#include "pld.h"

int count_palindromes(const std::string &A,
                      const std::string &B,
                      const std::string &C);

函数的返回值必须在 $[0,998244352]$ 内。

不要实现 main，不要进行标准输入输出。评测器可能在同一个进程中多次调用该函数，每次调用对应一个独立的问题。

数据范围与评分

对每次调用，记

$$ L=max(|A|,|B|,|C|). $$

保证 $1\le |A|,|B|,|C|\le10^5$，且三个串均仅包含小写英文字母。

同一个测试点内，所有调用的 $L$ 之和不超过 $10^5$。 调用次数不超过 $10^5$。不同字符串的长度不一定相同。

每个子任务采用捆绑评分。子任务 2 依赖子任务 1；子任务 4 依赖子任务 1、2、3。

样例调用

以下每一行均表示一次独立调用。

最后一次调用中，每个串均有三个非空子串，任意选取后拼接的字符串都是回文串，因此共有 $3^3=27$ 种方案。

本地测试

附件提供 pld.h、待填写的 solution.cpp、本地测试程序 grader.cpp。

可使用以下命令编译和运行：

g++ -std=c++17 -O2 -pipe grader.cpp solution.cpp -o grader
./grader < sample.in

本地测试程序的输入格式为：第一行一个整数 $T$，之后每组输入三行，依次为 $A,B,C$。程序每行输出一次函数调用的返回值。这个输入格式只用于本地测试。

Attachments

grader.cpp

#include "pld.h"
#include <iostream>
#include <string>

int main() {
    int T;
    if (!(std::cin >> T)) return 0;
    while (T--) {
        std::string A, B, C;
        std::cin >> A >> B >> C;
        std::cout << count_palindromes(A, B, C) << '\n';
    }
}

pld.h

#ifndef PLD_H
#define PLD_H
#include <string>

int count_palindromes(const std::string &A,
                      const std::string &B,
                      const std::string &C);
#endif

solution.cpp

#include "pld.h"

int count_palindromes(const std::string &A,
                      const std::string &B,
                      const std::string &C) {
    // Implement your algorithm here.
    return 0;
}

题目资源