2022 ICPC網路賽（二） G Good Permutation
題意：
? 現在有一個長度為n的排列，現在給出m組約束條件，請問有多少種方案滿足這個約束條件，
? 約束條件：給出l, r，表示\([l, r]\)這個區間中的最大值-最小值等于\(r - l\)，
思路：
? 對于約束條件l，r可以進一步轉化，轉化為在[l, r]區間中放置一段連續的數字，
? 題目中特別提到了，給出的約束區間是不會相交的，這樣就可以做了，對于樣例[1, 5], [1, 4], [1, 3]，我們可以思考一下怎么求解，如果只有一個約束條件[1, 3]的話，那么答案應該是把[1, 3]打包成一個，內部全排列，和外面的2個點一起全排列，我們發現[1, 4]和[1, 3]，還有[1, 4]和[1, 5]是存在一個遞回關系的，通過手動計算，發現答案符合樣例，那么我們思考怎么完成這個遞回的程序，
? 由于這個區間包含的關系看起來是個樹形結構，所以我們考慮對這些約束條件建樹，區間長度大的包含著區間長度小的，可以得到一個樹形結構，這樣我們從[1, n]的區間開始做一次樹形DP就可以了，
區間u的方案數就是被其包含的所有子區間v的方案數的乘積 乘上 這個區間內的有多少團東西的全排列的方案數，
\[f[u] = \prod{f[v]} * fac[len[u] - lensum + cnt]; \]實作：
const int mod = 1e9 + 7;
const int N = 1000005;
int n, m;
vector<int> g[N];
PII a[N];
ll fac[N];
stack<int> stk;
bool cmp(PII a, PII b)
{
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
ll len(PII v) {return v.second - v.first + 1;}
void init()
{
fac[0] = 1; for(int i = 1; i < N; i ++) fac[i] = fac[i - 1] * i % mod;
}
ll dfs(int u)
{
ll res = 1;
int cnt = 0, len = 0; //區間個數，區間長度
for(int v : g[u])
{
res *= dfs(v), res %= mod;
cnt ++;
len += len(a[v]);
}
res *= fac[len(a[u]) - len + cnt], res %= mod;
return res;
}
signed main()
{
scanf("%d%d", &n, &m);
init();
for(int i = 1; i <= m; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
a[i] = {x, y};
}
a[++ m] = {1, n};
sort(a + 1, a + m + 1, cmp);
m = unique(a + 1, a + m + 1) - (a + 1); //去重
stk.push(1); //單調堆疊構造樹形結構
for(int i = 2; i <= m; i ++)
{
while(stk.size() && a[i].first > a[stk.top()].second) stk.pop();
if(stk.size())
g[stk.top()].push_back(i), stk.push(i);
}
cout << dfs(1) << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511066.html
標籤：其他