题解：P11075 不等关系 加强版

这是洛谷转移过来的题解，作者是4041nofoundGeoge（我自己，记得关注呀）

题目大意

对于一个字符串 s 1 , s 2 , ⋯   , s n s_1,s_2,\cdots ,s_n s1​,s2​,⋯,sn​，仅包含 < 和 > 两种字符。

设 f ( s ) f(s) f(s) 为「使得 p i < p i + 1 p_i<p_{i+1} pi​<pi+1​ 当且仅当 s i s_i si​ 为 < 的排列 p 1 , p 2 , ⋯   , p n + 1 p_1,p_2,\cdots ,p_{n+1} p1​,p2​,⋯,pn+1​」的数量。

现在请你求出，对于所有 2 n 2^n 2n 种长度为 n n n 的字符串 s s s， f ( s ) f(s) f(s) 之和是多少。

由于答案可能有点大，因此你只需要输出它对 998244353 998244353 998244353 取模的结果。

思路

看起来说的很玄乎，但是仔细分析可以发现重点就在这句话：

设 f ( s ) f(s) f(s) 为「使得 p i < p i + 1 p_i<p_{i+1} pi​<pi+1​ 当且仅当 s i s_i si​ 为 < 的排列 p 1 , p 2 , ⋯   , p n + 1 p_1,p_2,\cdots ,p_{n+1} p1​,p2​,⋯,pn+1​」的数量。

突破口就在排列两字。通过题面给的运算符共有 n n n 个，对印的字符就有 n + 1 n+1 n+1 个。把 n + 1 n+1 n+1 个字符排列一下，即得到 A n + 1 n + 1 A^{n+1}_{n+1} An+1n+1​，换种写法即 ( n + 1 ) ! (n+1)! (n+1)!。思路清晰，就可以写了。

坑点

千万要记得开 long long 并且还要模 998244353 998244353 998244353！

代码

我献上我丑陋的代码：

//c++版本
#include<iostream>
using namespace std;
long long sum=1;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n+1;++i)sum=sum*i%998244353;
	printf("%d",sum);
	
}

java 代码：

import java.util.Scanner;  
public class Main {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
        long sum = 1;   
        for (int i = 1; i <= n+1; ++i) {  
            sum = (sum * i) % 998244353;
        }  
          
        System.out.println(sum);  
        scanner.close(); 
    }  
}

python 代码：

x=int(input(""))
sum=1
for i in range(1,x+2):
    sum=sum*i%998244353
print(sum)