题解 | 奶牛排排站

用排列组合的思想其实也能得到和康托展开差不多的式子，想清楚当前位对排位的贡献就行了

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	public static void main(String[] args) throws IOException {
		new Task().main();
	}

	static int n, m, maxn = 200005, inf = 0x3f3f3f3f;
	static long ans = 0, mod = (int) 1e9 + 7, INF = (long) 2e18;
	

	static class Task {
		void main() throws IOException {
			int t = 1;
			//t=sc.nextI();
			while (t-- > 0)
				solve();
			pw.flush();
		}
		
		void solve() throws IOException {
			n = sc.nextI();
			m = sc.nextI();
			long []fac = new long[22];
			fac[0] = 1;
			for(int i=1;i<=20;i++) {
				fac[i] = fac[i-1]*i;
			}
			while(m-->0) {
				String op = sc.next();
				if(op.equals("P")) {
					long a = sc.nextL();
					boolean []f = new boolean[n+2];
					for(int i=1;i<=n;i++) {
						int p = 1;
						int cnt = 0;
						for(int j=1;j<=n;j++) {
							if(f[j]) continue;
							cnt++;
							if(fac[n-i]*cnt < a) {
								p = j;
							}
							else {
								p=j;
								break;
							}
						}
						a -= fac[n-i]*(cnt-1);
						f[p] = true;
						pw.print(p+" ");
					}
					pw.println("");
				}
				else {
					boolean []f = new boolean[n+2];
					ans = 0;
					for(int i=1;i<=n;i++) {
						int x = sc.nextI();
						int cnt = 0;
						for(int j=1;j<x;j++) if(!f[j]) cnt++;
						f[x] = true;
						ans += fac[n-i] * cnt;
					}
					pw.println(ans+1);
				}
			}
			
		}
	}
	
	
	
	static class Input {
        Input(InputStream in) { this.in = in; } InputStream in;
        byte[] bb = new byte[1 << 15]; int i, n;
        byte getc() {
                    if (i == n) {
                i = n = 0;
        try { n = in.read(bb); } catch (IOException e) {}
            }
            return i < n ? bb[i++] : 0;
        }
        int nextI() {
            byte c = 0; while (c <= ' ') c = getc();
            int f=1;
            int a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
            return a*f;
        }
        long nextL() {
            byte c = 0; while (c <= ' ') c = getc();
            int f=1;
            long a = 0; while (c > ' ') { if(c=='-') {f=-1;c = getc();continue;}a = a * 10 + c - '0'; c = getc(); }
            return a*f;
        }
        byte[] cc = new byte[1 << 7];
        String next() {
            byte c = 0; while (c <= ' ') c = getc();
            int k = 0;
            while (c > ' ') {
                if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1);
                cc[k++] = c; c = getc();
            }
            return new String(cc, 0, k);
        }
    }
	
	static class Output{
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sss = new StringBuilder();
		
		void flush() throws IOException {
			bw.write(sss.toString());
			bw.flush();
		}
		
		void print(Object x) throws IOException {
			sss.append(x);
			if(sss.length()>10000) {
				bw.write(sss.toString());
				sss.setLength(0);
			}
		}
		void println(Object x) throws IOException {
			sss.append(x);
			sss.append('\n');
			if(sss.length()>10000) {
				bw.write(sss.toString());
				sss.setLength(0);
			}
		}
		
	}

	static Input sc = new Input(System.in);
	static Output pw = new Output();
}