Kaavi and Magic Spell - VietMX's Blog

Kaavi, the mysterious fortune teller, deeply believes that one’s fate is inevitable and unavoidable. Of course, she makes her living by predicting others’ future. While doing divination, Kaavi believes that magic spells can provide great power for her to see the future.

Kaavi has a string $T$ of length $m$ and all the strings with the prefix $T$ are magic spells. Kaavi also has a string $S$ of length $n$ and an empty string $A$.

During the divination, Kaavi needs to perform a sequence of operations. There are two different operations:

Delete the first character of $S$ and add it at the front of $A$.
Delete the first character of $S$ and add it at the back of $A$.

Kaavi can perform no more than $n$ operations. To finish the divination, she wants to know the number of different operation sequences to make $A$ a magic spell (i.e. with the prefix $T$). As her assistant, can you help her? The answer might be huge, so Kaavi only needs to know the answer modulo $998\,244\,353$.

Two operation sequences are considered different if they are different in length or there exists an $i$ that their $i$-th operation is different.

A substring is a contiguous sequence of characters within a string. A prefix of a string $S$ is a substring of $S$ that occurs at the beginning of $S$.Input

The first line contains a string $S$ of length $n$ ($1 \leq n \leq 3000$).

The second line contains a string $T$ of length $m$ ($1 \leq m \leq n$).

Both strings contain only lowercase Latin letters.Output

The output contains only one integer — the answer modulo $998\,244\,353$.Examplesinput

abab
ba

output

input

defineintlonglong
signedmain

output

input

rotator
rotator

output

input

cacdcdbbbb
bdcaccdbbb

output

Note

The first test:

The red ones are the magic spells. In the first operation, Kaavi can either add the first character “a” at the front or the back of $A$, although the results are the same, they are considered as different operations. So the answer is $6\times2=12$.

Solution:

#include &lt;bits/stdc++.h&gt;

using namespace std;

template &lt;typename A, typename B&gt;
string to_string(pair&lt;A, B&gt; p);

template &lt;typename A, typename B, typename C&gt;
string to_string(tuple&lt;A, B, C&gt; p);

template &lt;typename A, typename B, typename C, typename D&gt;
string to_string(tuple&lt;A, B, C, D&gt; p);

string to_string(const string&amp; s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

string to_string(vector&lt;bool&gt; v) {
bool first = true;
string res = "{";
for (int i = 0; i &lt; static_cast&lt;int&gt;(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}

template &lt;size_t N&gt;
string to_string(bitset&lt;N&gt; v) {
string res = "";
for (size_t i = 0; i &lt; N; i++) {
    res += static_cast&lt;char&gt;('0' + v[i]);
}
return res;
}

template &lt;typename A&gt;
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &amp;x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

template &lt;typename A, typename B&gt;
string to_string(pair&lt;A, B&gt; p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template &lt;typename A, typename B, typename C&gt;
string to_string(tuple&lt;A, B, C&gt; p) {
return "(" + to_string(get&lt;0&gt;(p)) + ", " + to_string(get&lt;1&gt;(p)) + ", " + to_string(get&lt;2&gt;(p)) + ")";
}

template &lt;typename A, typename B, typename C, typename D&gt;
string to_string(tuple&lt;A, B, C, D&gt; p) {
return "(" + to_string(get&lt;0&gt;(p)) + ", " + to_string(get&lt;1&gt;(p)) + ", " + to_string(get&lt;2&gt;(p)) + ", " + to_string(get&lt;3&gt;(p)) + ")";
}

void debug_out() { cerr &lt;&lt; endl; }

template &lt;typename Head, typename... Tail&gt;
void debug_out(Head H, Tail... T) {
cerr &lt;&lt; " " &lt;&lt; to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr &lt;&lt; "[" &lt;&lt; #__VA_ARGS__ &lt;&lt; "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template &lt;typename T&gt;
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}

template &lt;typename T&gt;
class Modular {
public:
using Type = typename decay&lt;decltype(T::value)&gt;::type;

constexpr Modular() : value() {}
template &lt;typename U&gt;
Modular(const U&amp; x) {
value = normalize(x);
}

template &lt;typename U&gt;
static Type normalize(const U&amp; x) {
Type v;
if (-mod() &lt;= x &amp;&amp; x &lt; mod()) v = static_cast&lt;Type&gt;(x);
else v = static_cast&lt;Type&gt;(x % mod());
if (v &lt; 0) v += mod();
    return v;
  }

  const Type&amp; operator()() const { return value; }
  template &lt;typename U&gt;
explicit operator U() const { return static_cast&lt;U&gt;(value); }
constexpr static Type mod() { return T::value; }

Modular&amp; operator+=(const Modular&amp; other) { if ((value += other.value) &gt;= mod()) value -= mod(); return *this; }
Modular&amp; operator-=(const Modular&amp; other) { if ((value -= other.value) &lt; 0) value += mod(); return *this; }
  template &lt;typename U&gt; Modular&amp; operator+=(const U&amp; other) { return *this += Modular(other); }
template &lt;typename U&gt; Modular&amp; operator-=(const U&amp; other) { return *this -= Modular(other); }
Modular&amp; operator++() { return *this += 1; }
Modular&amp; operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }

template &lt;typename U = T&gt;
typename enable_if&lt;is_same&lt;typename Modular&lt;U&gt;::Type, int&gt;::value, Modular&gt;::type&amp; operator*=(const Modular&amp; rhs) {
#ifdef _WIN32
uint64_t x = static_cast&lt;int64_t&gt;(value) * static_cast&lt;int64_t&gt;(rhs.value);
uint32_t xh = static_cast&lt;uint32_t&gt;(x &gt;&gt; 32), xl = static_cast&lt;uint32_t&gt;(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast&lt;int64_t&gt;(value) * static_cast&lt;int64_t&gt;(rhs.value));
#endif
return *this;
}
template &lt;typename U = T&gt;
typename enable_if&lt;is_same&lt;typename Modular&lt;U&gt;::Type, int64_t&gt;::value, Modular&gt;::type&amp; operator*=(const Modular&amp; rhs) {
int64_t q = static_cast&lt;int64_t&gt;(static_cast&lt;long double&gt;(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template &lt;typename U = T&gt;
typename enable_if&lt;!is_integral&lt;typename Modular&lt;U&gt;::Type&gt;::value, Modular&gt;::type&amp; operator*=(const Modular&amp; rhs) {
value = normalize(value * rhs.value);
return *this;
}

Modular&amp; operator/=(const Modular&amp; other) { return *this *= Modular(inverse(other.value, mod())); }

template &lt;typename U&gt;
friend const Modular&lt;U&gt;&amp; abs(const Modular&lt;U&gt;&amp; v) { return v; }

template &lt;typename U&gt;
friend bool operator==(const Modular&lt;U&gt;&amp; lhs, const Modular&lt;U&gt;&amp; rhs);

template &lt;typename U&gt;
friend bool operator&lt;(const Modular&lt;U&gt;&amp; lhs, const Modular&lt;U&gt;&amp; rhs);

template &lt;typename U&gt;
friend std::istream&amp; operator&gt;&gt;(std::istream&amp; stream, Modular&lt;U&gt;&amp; number);

private:
Type value;
};

template &lt;typename T&gt; bool operator==(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return lhs.value == rhs.value; }
template &lt;typename T, typename U&gt; bool operator==(const Modular&lt;T&gt;&amp; lhs, U rhs) { return lhs == Modular&lt;T&gt;(rhs); }
template &lt;typename T, typename U&gt; bool operator==(U lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) == rhs; }

template &lt;typename T&gt; bool operator!=(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return !(lhs == rhs); }
template &lt;typename T, typename U&gt; bool operator!=(const Modular&lt;T&gt;&amp; lhs, U rhs) { return !(lhs == rhs); }
template &lt;typename T, typename U&gt; bool operator!=(U lhs, const Modular&lt;T&gt;&amp; rhs) { return !(lhs == rhs); }

template &lt;typename T&gt; bool operator&lt;(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return lhs.value &lt; rhs.value; }

template &lt;typename T&gt; Modular&lt;T&gt; operator+(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) += rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator+(const Modular&lt;T&gt;&amp; lhs, U rhs) { return Modular&lt;T&gt;(lhs) += rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator+(U lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) += rhs; }

template &lt;typename T&gt; Modular&lt;T&gt; operator-(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) -= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator-(const Modular&lt;T&gt;&amp; lhs, U rhs) { return Modular&lt;T&gt;(lhs) -= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator-(U lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) -= rhs; }

template &lt;typename T&gt; Modular&lt;T&gt; operator*(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) *= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator*(const Modular&lt;T&gt;&amp; lhs, U rhs) { return Modular&lt;T&gt;(lhs) *= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator*(U lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) *= rhs; }

template &lt;typename T&gt; Modular&lt;T&gt; operator/(const Modular&lt;T&gt;&amp; lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) /= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator/(const Modular&lt;T&gt;&amp; lhs, U rhs) { return Modular&lt;T&gt;(lhs) /= rhs; }
template &lt;typename T, typename U&gt; Modular&lt;T&gt; operator/(U lhs, const Modular&lt;T&gt;&amp; rhs) { return Modular&lt;T&gt;(lhs) /= rhs; }

template&lt;typename T, typename U&gt;
Modular&lt;T&gt; power(const Modular&lt;T&gt;&amp; a, const U&amp; b) {
assert(b &gt;= 0);
Modular&lt;T&gt; x = a, res = 1;
U p = b;
while (p &gt; 0) {
if (p &amp; 1) res *= x;
x *= x;
p &gt;&gt;= 1;
}
return res;
}

template &lt;typename T&gt;
bool IsZero(const Modular&lt;T&gt;&amp; number) {
return number() == 0;
}

template &lt;typename T&gt;
string to_string(const Modular&lt;T&gt;&amp; number) {
return to_string(number());
}

template &lt;typename T&gt;
std::ostream&amp; operator&lt;&lt;(std::ostream&amp; stream, const Modular&lt;T&gt;&amp; number) {
return stream &lt;&lt; number();
}

template &lt;typename T&gt;
std::istream&amp; operator&gt;&gt;(std::istream&amp; stream, Modular&lt;T&gt;&amp; number) {
typename common_type&lt;typename Modular&lt;T&gt;::Type, int64_t&gt;::type x;
stream &gt;&gt; x;
number.value = Modular&lt;T&gt;::normalize(x);
return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType&amp; md = VarMod::value;
using Mint = Modular&lt;VarMod&gt;;
*/

constexpr int md = 998244353;
using Mint = Modular&lt;std::integral_constant&lt;decay&lt;decltype(md)&gt;::type, md&gt;&gt;;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin &gt;&gt; s;
string t;
cin &gt;&gt; t;
int n = (int) s.size();
int orig = (int) t.size();
int nt = (int) t.size();
while (nt &lt; n) {
    t += "?";
    nt += 1;
  }
  vector&lt;Mint&gt; dp(n + 1);
dp[0] = 1;
for (int pos = n - 1; pos &gt;= 0; pos--) {
vector&lt;Mint&gt; new_dp(n + 1);
for (int i = 0; i + pos &lt; n; i++) {
      int j = i + pos;
      if (s[pos] == t[i] || t[i] == '?') {
        if (i &gt; 0) {
new_dp[i + 1] += dp[i];
} else {
int ways = min(n - pos, n - orig + 1);
new_dp[i + 1] += dp[i] * ways;
}
}
if (s[pos] == t[j] || t[j] == '?') {
new_dp[i] += dp[i];
}
}
swap(dp, new_dp);
}
Mint ans = accumulate(dp.begin(), dp.end(), Mint(0));
cout &lt;&lt; ans &lt;&lt; '\n';
  return 0;
}

Potions Homework

Little Artem and 2-SAT

Packmen

Fish Weight

Chat Order

Dijkstra on sparse graphs

Coffee Varieties (hard version)

Messy

Restoring Map

Rotate Columns (easy version)

Sharti

Extended Euclidean Algorithm