Trò chơi ở đây.

B. Sự sắp xếp

Lời nói đầu:

dp trên cây Descartes? Cái tên này thật tuyệt vời, nhưng nó không thực sự yêu cầu cây Descartes, nó chỉ sử dụng định nghĩa của cây Descartes.

Thuộc tính: Chúng tôi đặt vị trí của giá trị lớn nhất trong một khoảng \([l,r]\) thành \(pos\) và thấy rằng khoảng đó có thể được chia thành \([l,pos]\) và \ ([pos ,r]\) hai khoảng con, và hai phần này không ảnh hưởng lẫn nhau, tức là dù tôi đặt số bên trái thế nào cũng không ảnh hưởng đến bên phải của tôi.

Lưu ý: Nếu bạn đã hiểu cây Descartes, thì các khoảng được đề cập dưới đây đề cập đến các khoảng trên cây Descartes, nếu bạn không biết về cây Descartes, tôi cần phải nói: khoảng được đề cập dưới đây đề cập đến một số mở rộng cho cả hai; cho đến khi số ở bên lớn hơn số này.

Như thể hiện trong hình bên dưới, toàn bộ khoảng được chia thành hai khoảng nhỏ.

sự định nghĩa:

Đặt \(f_{i,j,0/1}\) biểu thị số tùy chọn trong đó khoảng có độ dài \(i\) bị xóa hoàn toàn sau \(j\) lần.

1 có nghĩa là cả hai bên của khoảng đều liền kề với một số lớn hơn khoảng; 0 có nghĩa là một bên liền kề với một số lớn hơn số lớn nhất trong khoảng và bên còn lại là \([1,n]\ ) ranh giới của toàn bộ khoảng.

Theo định nghĩa, chúng ta thấy rằng rõ ràng là chúng ta không bao gồm toàn bộ khoảng \([1,n]\) trong \(f\) và không thể xóa tất cả các số trong toàn bộ khoảng.

Vì vậy, cuối cùng, câu trả lời cho toàn bộ khoảng được tính riêng biệt với giá trị dp của hai khoảng phụ của nó.

Xem xét chuyển dp:

• Đối với việc chuyển \(f_{i,j,1}\): chúng tôi liệt kê vị trí của giá trị lớn nhất trong khoảng \(k\) và với mỗi \(k\) chúng tôi tìm thấy \(\tbinom {i -1}{k-1}\) nghiệm (\(k-1\) là số khoảng ở bên trái giá trị lớn nhất).

  Vậy có sự chuyển giao:

  • Giá trị lớn nhất trong khoảng được xóa sau cùng, sau đó là khoảng bên trái và khoảng bên phải. \(j-1\) Số lần đã xóa:
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j-1,1}\times f_{nk,j-1,1}) \]
  • Giá trị lớn nhất ở khoảng bên phải được xóa sau cùng, khi đó giá trị lớn nhất của khoảng lớn là giá trị lớn hơn ở một bên của khoảng bên trái tại \(j\) Xóa trước lần:
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{nk,j,1}\times \sum_{l =1}^{j-1} f_{k-1,l,1}) \]
  • Giá trị lớn nhất ở khoảng bên trái được xóa sau cùng, tương tự:
  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j,1}\times \sum_ {l=1}^{j-1} f_{nk,l,1}) \]

  Trong hai trường hợp sau, phép tính tổng trong công thức có thể được thêm tiền tố và tối ưu hóa trực tiếp, đồng thời mảng \(s\) biểu thị sự kết hợp có tiền tố.

  Tóm tắt các lần chuyển tiền:

  \[f_{i,j,1} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j-1,1}\times f_{nk,j-1,1}+f_{nk,j,1}\times s_{k-1,l,1}+f_{k-1,j,1}\times s_{nk,l,1}) \]

• Đối với việc chuyển \(f_{i,j,0}\): vị trí của giá trị lớn nhất cũng được liệt kê và để tránh trùng lặp, rõ ràng chúng ta chỉ nên tính toán trường hợp một bên là ranh giới, do đó phía bên trái được chỉ định là ranh giới ( .

  Vì không có giá trị nào lớn hơn ở bên trái khoảng bên trái nên giá trị lớn nhất của khoảng chỉ có thể bị xóa bằng giá trị lớn hơn ở bên phải khoảng bên phải, do đó các số ở khoảng bên phải phải bị xóa trong phạm vi \ (j\) lần.

  Có sự chuyển giao:

  • Khoảng bên trái bị xóa trước khi giá trị tối đa của khoảng lớn bị xóa:
  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (\sum_{l=1}^{j-1} f_ {k-1,l,0} \times f_{nk,j-1,1}) \]
  • Giá trị lớn nhất ở khoảng bên trái cuối cùng bị xóa nên giá trị lớn nhất ở giữa là \(j\) bị xóa trong khoảng thời gian, tất cả các số trong khoảng bên phải đều nằm trong \(j-1\) Đã xóa trong thời gian:
  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (f_{k-1,j,0}\times \sum_ {l=1}^{j-2} f_{nk,l,1}) \]

  Tiền tố và tối ưu hóa tương tự ( , tóm tắt:

  \[f_{i,j,0} \leftarrow \sum_{k=1}^i \tbinom{i-1}{k-1}\times (s_{k-1,l,0}\times f_{ nk,j-1,1}+f_{k-1,j,0}\times s_{nk,l,1}) \]

độ phức tạp thời gian

Người ta thấy rằng mỗi thao tác sẽ xóa ít nhất một nửa số trong khoảng, do đó, một khoảng có độ dài \(i\) có thể bị xóa nhiều nhất \(\log i\) lần.

Trong quá trình dp, độ dài khoảng, số lần xóa và vị trí giá trị tối đa được liệt kê và độ phức tạp là \(O(n^2 \log)\).

Tính toán trả lời:

Có hai tình huống

1. Cả hai khoảng con đều bị xóa \(K\) lần.

2. Một dải con bị xóa sau \(K\) lần, trong khi dải con kia bị xóa sau \(K\) lần.

mã số:

#bao gồm #define Aqrfre(x, y) freopen(#x ".in", "r", stdin),freopen(#y ".out", "w", stdout) #define mp make_pair #define Loại ll #define qr(x) x=read() typedef __int128 INT typedef long long ll; nội tuyến ll read(){ char c=getchar(); ll x=0, f=1; while(!isdigit(c)) (c=='-'?f=-1:f=1), c= getchar(); while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar(); return x*f } const int N = 1005 ; int T, n, K, p, C[N][N]; int f[N][22][2], s[N][22][2]; nội tuyến void AqrPre(){ C[0] [0] = 1; for(int i=1; i<=n; i++){ C[i][0] = 1; for(int j=1; j<=i; j++){ C[i] [j] = (ll)(C[i-1][j] + C[i-1][j-1]) % p; } } } nội tuyến int qpow(int a, int b){ int res = 1; b){ if(b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; return res } main(){ // a // Aqrfre(a, a); qr(n); qr(p); if(K > 10){ put("0"); (K == 1){ cout<= 2 ? 1ll * f[k-1][j][0] * s[ik][j-2][1] : 0) % p) % p) % p; } s[i][j][1] = ( s[i] [j-1] + f[i] [j]) % p; ] + f[i][j][0]) % p; } } int ans = 0; for(int i=1; i<=n; i++){ ans = (ll)(ans + 1ll * C[n- 1][i-1] * (1ll * f[i-1][K][0] * f[ni][K][0] % p + 1ll * f[i-1][K][0 ] * s[ni][K-1][0] % p + 1ll * s[i-1][K-1][0] * f[ni][K][0] % p) % p) % p ; } cout<

Cuối cùng, bài viết này về [Hoán vị] (dp trên cây Descartes?) kết thúc ở đây. Nếu bạn muốn biết thêm về [Hoán vị] (dp trên cây Descartes?), vui lòng tìm kiếm bài viết CFSDN hoặc tiếp tục Duyệt qua các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .