目錄

排列游戲

題目描述

輸入描述:

輸出描述:

輸入

輸出

備注:

思路：

代碼：

---

?

排列游戲

K-排列游戲_牛客競賽動態規劃專題班習題課 (nowcoder.com)

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

你拿到了一個神秘的字符串，這個字符串的長度為n，里面只有0,1,2三種數。但是你意識到了事情并不簡單，這個字符串實際上隱藏的是一個長度為n+1的排列。我們將字符串和排列的下標從1開始標號，如果s[i]=1，那么說明排列aaa的第i位ai小于ai+1；如果s[i]=2，那么說明ai大于ai+1；如果s[i]=0，那么說明ai和ai+1?的關系任意。
現在你需要求出有多少種不同的排列滿足條件，輸出在模998244353意義下的答案。

（排列指的是 1 .... n 都出現了，并且只出現了一次）

輸入描述:

一行一個字符串S。

輸出描述:

輸出一個整數表示在模998244353意義下的答案。

示例1

輸入

102

輸出

6

備注:

1≤n≤5e3

思路：

dp[i][j] 表示前i位滿足要求，并且末尾小于等于j時的方案數。（邊求解并統計前綴和）

由于求得是(1到n+1的排列，所以不能有重復數字)。則我們要求前i位只能填1-i這些數字，那么第i+1位填了1-i的數字j怎么解決，那么就讓前i位大于等于j的數字加1，這樣還是保證了i+1位中沒有重復數字，并且也滿足了題目的需求。

轉移方程為
? ? ? ? ? ?當前位為?2? ? dp[i % 2][j] = (dp[(i - 1) % 2][i - 1] - dp[(i - 1) % 2][j - 1] + mod)% mod;
? ? ? ? ? ?當前位為?1? ?dp[i % 2][j] = dp[(i - 1) % 2][j - 1] % mod;?
? ? ? ? ? ?當前位為 0? ?dp[i % 2][j] = dp[(i - 1) % 2][i - 1] % mod;

代碼：

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;/*** @ProjectName: study3* @FileName: Ex8* @author:HWJ* @Data: 2023/12/8 10:59*/
public class Main {public static void main(String[] args) {String str = input.next();int mod = 998244353;char[] s = str.toCharArray();int n = s.length;int[][] dp = new int[2][n + 2];dp[1][1] = 1;for (int i = 2; i <= n + 1; i++) {for (int j = 1; j <= i; j++) {dp[i % 2][j] = 0;if (s[i - 2] == '2') {dp[i % 2][j] = (dp[(i - 1) % 2][i - 1] - dp[(i - 1) % 2][j - 1] + mod)% mod;} else if (s[i - 2] == '1') {dp[i % 2][j] = dp[(i - 1) % 2][j - 1] % mod;} else {dp[i % 2][j] = dp[(i - 1) % 2][i - 1] % mod;}}for (int j = 1; j <= i; j++) {dp[i % 2][j] = (dp[i % 2][j - 1] + dp[i % 2][j]) % mod;}}out.println(dp[(n + 1) % 2][n + 1]);out.flush();out.close();}static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自動生成的 catch 塊e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}