ABC130-E Common Subsequence

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 2");
            WillReturn.Add("1 3");
            WillReturn.Add("3 1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4");
            WillReturn.Add("3 4 5 6");
            WillReturn.Add("3 4 5 6");
            //16
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 9");
            WillReturn.Add("9 6 5 7 5 9 8 5 6 7");
            WillReturn.Add("8 6 8 5 5 7 9 9 7");
            //191
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("20 20");
            WillReturn.Add("1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1");
            WillReturn.Add("1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1");
            //846527861
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] SArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] TArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long UB_X = SArr.GetUpperBound(0);
        long UB_Y = TArr.GetUpperBound(0);

        // 一致する部分文字列の数[文字列Sの末尾,文字列Tの末尾]なDP表
        long[,] BanArr = new long[UB_X + 1, UB_Y + 1];

        // 二次元累積和
        long[,] RunSumArr = new long[UB_X + 1, UB_Y + 1];

        // 範囲外なら1、範囲外でなければ、配列の値を返す
        Func<long, long, long> GetFunc = (pX, pY) =>
        {
            if (pX < 0 || pY < 0) return 1;
            return BanArr[pX, pY];
        };

        for (long X = 0; X <= UB_X; X++) {
            long AddVal = 0;
            for (long Y = 0; Y <= UB_Y; Y++) {

                // 一致したら、左上の長方形の値+1
                if (SArr[X] == TArr[Y]) {
                    long RectRunSum;
                    if (X == 0) {
                        RectRunSum = 0;
                    }
                    else if (Y == 0) {
                        RectRunSum = 0;
                    }
                    else {
                        RectRunSum = RunSumArr[X - 1, Y - 1];
                    }
                    BanArr[X, Y] = RectRunSum + 1;
                    BanArr[X, Y] %= Hou;
                }
                else {
                    BanArr[X, Y] = 0;
                }

                // 累積和を更新
                AddVal += BanArr[X, Y];
                AddVal %= Hou;

                RunSumArr[X, Y] += AddVal;
                RunSumArr[X, Y] %= Hou;
            }

            if (X < UB_X) {
                for (long Y = 0; Y <= UB_Y; Y++) {
                    RunSumArr[X + 1, Y] = RunSumArr[X, Y];
                }
            }
        }

        long Answer = 0;
        for (long X = 0; X <= UB_X; X++) {
            for (long Y = 0; Y <= UB_Y; Y++) {
                Answer += BanArr[X, Y];
                Answer %= Hou;
            }
        }

        // 空の文字列の分を足す
        Answer++;
        Answer %= Hou;
        Console.WriteLine(Answer);
    }
}

解説

ABCDという文字列同士で
一致する部分文字列の数[文字列Sの末尾,文字列Tの末尾]なDP表を考えると
不一致なら0
一致したら、(0からS-1,0からT-1)からなる長方形の場合の総和+1
になります。

  A B C D
A 1 0 0 0
B 0 2 0 0
C 0 0 3 0
D 0 0 0 7

あとは、結果を集計して空文字の分の1を足せば
解になります。

長方形の場合の数の総和は、二次元累積和で求めるようにしてます。