算法

(打表) $O(n)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;

public class Main {
    static BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter cout=new PrintWriter(new OutputStreamWriter(System.out));
    static int[] fin;
    static long mod=998244353;
    public static void main(String[] args) throws IOException {
        //dp问题?数学问题？复杂度要是n/nlogn
        //怎么写？肯定不能直接枚举全部排列
        //入手点应该是每个数在全排列的位置与权值的关系，所有数在所有位置的所有权值和为res
        //无论什么排列1都是0
        //尝试打表

        //      int[] arr= {1,2,3,4,5,6};
//      fin=new int[arr.length+1];
//      dfs(arr,0);
//      for(int i=1;i<fin.length;i++) {
//          cout.print(fin[i]+" ");
//      }

        //1          0
        //12         0  1
        //123        0  3   6
        //1234       0  12  24   36
        //12345      0  60  120  180  240
        //发现每行是首元素递增倍数，而且首元素是1 3 3*4 3*4*5 3*4*5*6 //从n=3开始首元素正好是3乘到n的数
        //写完之后试试发现n=0 1 2也是对的，不用特判了

        //数学规律发现!

        //这样是7/10,猜测应该是new big太慢，但是很难取舍，如下面我就错了
        //我怕遇到取模出错，时间够到是可以尝试(还是对取模的题见得少)
//      int n=Integer.parseInt(cin.readLine());
//      BigInteger res=new BigInteger("0");
//      BigInteger first=new BigInteger("1");
//      for(long i=3;i<=n;i++) {    
//          first=first.multiply(new BigInteger(i+""));
//      }
//      //求1-n-1的和
//      long sum=((n-1)*(1+n-1))/2;
//      res=first.multiply(new BigInteger(sum+""));
//      
//      
//      cout.println(res.mod(new BigInteger("998244353")));

        //尝试long
        int n=Integer.parseInt(cin.readLine());
        long res=0;
        long first=1;
        for(long i=3;i<=n;i++) {    
            first=(first*i)%mod;
//          first=((first%mod)*(i%mod))%mod;//这样还是爆
        }
//      long sum=(((n-1)*(1+n-1))/2)%mod;//这样也不行
        long sum = ((n-1) % mod * ((1+n-1) % mod) / 2) % mod;//这样才行，取模真是太复杂了

//      cout.println(((first%mod)*(sum%mod))%mod);
        cout.println((first*sum)%mod);
        cin.close();
        cout.flush();
    }

    private static void dfs(int[] arr, int index) {//打表部分
        if(index==arr.length) {
            for(int i=0;i<arr.length;i++) {
//              cout.print(arr[i]+" ");
            }
//          cout.print(":");
            for(int i=1;i<arr.length;i++) {
                int tmp=0;
                for(int j=0;j<i;j++) {
                    if(arr[j]<arr[i]) {
                        tmp++;
                    }
                }
                fin[arr[i]]+=tmp;
            }
            for(int i=1;i<=arr.length;i++) {
//              cout.print(i+"数目："+res[i]+" ");
            }
//          cout.println();
            return;
        }
        for(int i=index;i<arr.length;i++) {
            int tmp=arr[i];
            arr[i]=arr[index];
            arr[index]=tmp;
            dfs(arr, index+1);
            tmp=arr[i];
            arr[i]=arr[index];
            arr[index]=tmp;
        }

    }

}