202006-4 1246

输入输出样例

样例1

输入

9
26

输出

5

样例2

输入

2020
16

输出

292008622

题解一

最简单的DP，仅考虑s长为1的情况。能混32分。

import java.util.Scanner;
public class Main {
    final static private int C = 998244353;
    public static void main(String[] args) {
        final int[] TRANS = new int[] { 0, 0, 1, 0, 2, 0, 3 };
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();
        int[][] dp = new int[n + 1][4];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i - 1][2];
            dp[i][1] = dp[i - 1][0];
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % C;
            dp[i][3] = (dp[i - 1][2] + dp[i - 1][3]) % C;
        }
        System.out.println(dp[n][TRANS[s]]);
    }
}

题解二

把S=2的情况也考虑进来，能拿64分。

import java.util.Scanner;
public class Main {
    final static private int C = 998244353;
    public static void main(String[] args) {
        final int[] NUM = new int[] { 1, 2, 4, 6, 16, 26, 41, 42, 44, 46, 61, 62, 64, 66 };
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();
        int[][] dp = new int[n + 1][NUM.length];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i - 1][2];
            dp[i][1] = dp[i - 1][0];
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % C;
            dp[i][3] = (dp[i - 1][2] + dp[i - 1][3]) % C;
            dp[i][4] = dp[i - 1][2];
            dp[i][5] = dp[i - 1][4];
            dp[i][6] = dp[i - 1][12];
            dp[i][7] = dp[i - 1][10];
            dp[i][8] = dp[i - 1][11];
            dp[i][9] = (dp[i - 1][5] + dp[i - 1][13]) % C;
            dp[i][10] = dp[i - 1][8];
            dp[i][11] = dp[i - 1][6];
            dp[i][12] = (dp[i - 1][3] + dp[i - 1][7]) % C;
            dp[i][13] = dp[i - 1][9];
        }
        for (int i = 0; i < NUM.length; ++i) {
            if (NUM[i] == s) {
                System.out.println(dp[n][i]);
                break;
            }
        }
    }
}