TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P8008
  • 問題
  • P8008[NOI Online 2021] 积木小赛
    制限 : 時間制限 : - MS   メモリ制限 : 262144 KB
    審判説明 : 1s,256MB
    問題説明

    Alice和Bob最近热衷于玩一个游戏——积木小赛。

    Alice和Bob初始时各有 \(n\) 块积木从左至右排成一排,每块积木都被标上了一个英文小写字母。

    Alice可以从自己的积木中丢掉任意多块(也可以不丢);Bob可以从自己的积木中丢掉最左边的一段连续的积木和最右边的一段连续的积木(也可以有一边不丢或者两边都不丢)。两人都不能丢掉自己所有的积木。然后Alice和Bob会分别将自己剩下的积木按原来的顺序重新排成一排。

    Alice和Bob都忙着去玩游戏了,于是想请你帮他们算一下,有多少种不同的情况下他们最后剩下的两排积木是相同的。

    两排积木相同,当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。两种情况不同,当且仅当Alice(或者Bob)剩下的积木在两种情况中不同。

    入力形式

    第一行一个正整数 \(n\) ,表示积木的块数。

    第二行一个长度为 \(n\) 的小写字母串 \(s\) ,表示Alice初始的那一排积木,其中第 \(i\) 个字母 \(s_i\) 表示第 \(i\) 块积木上的字母。

    第三行一个长度为 \(n\) 的小写字母串 \(t\) ,表示Bob初始的那一排积木,其中第 \(i\) 个字母 \(t_i\) 表示第 \(i\) 块积木上的字母。

    出力形式

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

    サンプル入力 1

    5
    bcabc
    bbcca

    サンプル出力 1

    9

    サンプル入力 2

    20
    egebejbhcfabgegjgiig
    edfbhhighajibcgfecef

    サンプル出力 2

    34

    ヒント

    样例1解释

    用所标的字母代替每块积木,那么Alice剩下的那排积木依序为 \(\texttt{a}\)\(\texttt{b}\)\(\texttt{bb}\)\(\texttt{bbc}\)\(\texttt{bc}\)\(\texttt{bcc}\)\(\texttt{c}\)\(\texttt{ca}\) 或者 \(\texttt{cc}\) 时,Bob剩下的那排积木可以与Alice的相同。

    数据范围

    对于所有测试点: \(1\leq n\leq 3000\)\(s\)\(t\) 中只包含英文小写字母。

    测试点 $1$ 满足: \(n\leq 3000\)\(s\)\(t\) 中只包含同一种字母。
    测试点 \(2\sim4\) 满足: \(n\leq 100\)
    测试点 \(5\sim7\) 满足: \(n\leq 500\)
    测试点 \(8\sim10\) 满足: \(n\leq 3000\)