D.Valid Bitonic Permutations
算法本质
dp、思维
题目大意
生产一个长度为n的排列，且要求这个排列为单峰形式（先上后下——峰值不在边缘）
并且会明确规定排列的某2个下标对应的值，求数目。
思路推演-1
看了部分题解，才发现有dp的解题方式。
dp方法的核心在于，是否能构建一个具有一定传递性的的意义。
以dp[l][r]=x，表示在下标[l, r]中（共r-l+1个位置），有从n、n-1、n-2...n-r+l这r-l+1个数，其能构成合格的单峰数目为x
上面这句话比较重要，需要完全理解。
所以当我们考虑，dp[l][r]扩展到dp[l-1][r]时可以发现，我们实际上是把多加的一个数字放于最左边。
同理，扩展到dp[l][r+1]时可以发现，我们实际上是把多加的一个数字放在最右边。
思考单峰排列的构造，我们也是会先讲n放于中间，然后在左右两边添加较小值。而这个dp的思考方式即如此，同时配合固定下标，可以完成其对下标的要求。
由此，也可以知道，dp的起点应该从dp[i][i]=1，同时发现单峰不允许峰值在边缘，所以dp[1][1]=dp[n][n]=0。
同时在转移的过程中，需要注意的是得满足确定的2个下标+值这个条件，只需要在每次转移的过程中，检查一下是否满足，要是不满足就放弃这个转移即可。
ac核心代码-思路1
头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[105][105];
int p1, p2, v1, v2;
bool check(int pos, int val) //检查pos位置放val值可行否
{
if (pos==p1 && val!=v1) return 0;
if (pos==p2 && val!=v2) return 0;
return 1;
}
inline void solve()
{
//init
mem(dp, 0);
cin>>n>>p1>>p2>>v1>>v2;
for (int i=2; i<=n-1; i++)
if (check(i, n))
dp[i][i]=1;
//cal
for (int len=2; len<=n; len++)
{
for (int l=1; l+len-1<=n; l++)
{
int r=l+len-1;
//可以看作dp[l+1][r]加了一个数在左边
if (check(l, n-len+1))
dp[l][r] += dp[l+1][r];
//可以看作d[l][r-1]加了一个数在右边
if (check(r, n-len+1))
dp[l][r] += dp[l][r-1];
dp[l][r] %= mod;
}
}
//out
ans = dp[1][n];
cout<<ans<<endl;
return;
}思路推演-2
这里的思路推演请结合代码、图片（暂懒得画）一起看。
目前的条件有：单峰形式、确定的2个下标+值。
这两个条件能创造出的情景就相对有限，所以第一时间想到的是分类组合数。
这里的分类组合数也有2个解法，一是O(n^2^)每次枚举n出现的位置，这样的组合数也相对好写，下面这个题解中的D组合数方法就是这样写的：
Codeforces Round #840 (Div. 2) and Enigma 2022 - Cybros LNMIIT A~E
还有一个究极分类讨论方法，预处理组合数O(nlog~2~n)，每次O(n)，下面讲解：
首先我们讨论分类的情况，可以发现的是，这个线性模型对称，所以我们可以保证确定的2个值，在左边的一定更小。
这里l r表示2个确定值的下标，vl vr表示2个确定值的值：
int l, r, vl, vr; //l r为下标，vl vr为值
cin>>n>>l>>r>>vl>>vr;
if (vl > vr) //等价替换，保证左边的值一定小于右边
{
l = n-l+1;
r = n-r+1;
swap(l, r);
swap(vl, vr);
}加上单峰曲线，这样就可以分为2种情况：
- 右值恰好为n（特殊情况）
右值不为n
如果右值不为n，我们则需要讨论n出现的位置可能：l r n：峰值n出现r的右边l n r：峰值n出现在l r的中间
同时，我们也找到这个模型的一些公有变量。
以下标为横轴，我们可以分为3个位置：小于l、l r之间、大于r。
不同位置所拥有的位置个数，分别命名为：l_wei m_wei r_wei。
以值大小为纵轴，我们也可以分为3种大小的值：小于vl、vl vr之间、大于vr。
不同大小的值的个数，分别命名为：l_val m_val r_val。
固定2个确实位置+值这个条件我们已经做到了，接下来的构造中，需要保证确定是单峰这个条件。
右值恰好为n（特殊情况）（
vr==n）当
r==n时，这个时候不是单峰，则ans=0。
如果r!=n的话，我们以横轴为基准，先填充左边的下标，然后填充中间的，剩下的在右边摆好即可：ans = C(l_val, l_wei) * C(m_val, m_wei)右值不为n（
vr!=n）这里有2个可能：
l r n：峰值n出现r的右边还是先填充左边、再填充中间：
C(l_val, l_wei) * C(m_val, m_wei)
值大于vr的那些数（共r_val个），会自动填充在右边的，考虑他们的结构问题，可知结构个数：qpow(2, r_val-1)
同时想一想，这种情况可能导致非单峰的出现，在某个特点情况下，可能会导致n被放于最右边，那个时候需要结构个数-1l n r：峰值n出现在l r的中间先填充左边、再把值大于vr的那些数（共r_val个）强制填入中间，并考虑结构个数，最后把中间剩下的部分填满
最后最后剩下的数字填充右边即可。
这样就搞定了所有情况了。
ac核心代码-思路2
头文件、宏定义、快读模板、常见变量、常见变量等略。
//注：qpow默认对mod取模！
//组合数板子
int fac[maxn],inv[maxn]; //fac[x]代表x!，inv[x]代表x的逆元
void init_c(int max_num=maxn-2)
{
max_num = min(max_num, mod-1); //大于等于mod的情况用lucas定理
inv[0]=fac[0]=1;
for(int i=1;i<=max_num;i++) fac[i]=fac[i-1]*i%mod;
inv[max_num]=qpow(fac[max_num], mod-2, mod);
for(int i=max_num-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int a,int b) //C(下，上)
{
if(a<b) return 0;
if (a<0 || b<0) return 0;
if(a>=mod || b>=mod) return C(a%mod, b%mod)*C(a/mod, b/mod)%mod; //lucas定理，处理mod较小情况
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
inline void solve()
{
//init
int l, r, vl, vr; //l r为下标，vl vr为值
cin>>n>>l>>r>>vl>>vr;
if (vl > vr) //等价替换，保证左边的值一定小于右边
{
l = n-l+1;
r = n-r+1;
swap(l, r);
swap(vl, vr);
}
//cal
int l_wei=l-1; //左边的位置个数
int m_wei=r-l-1; //中间的
int r_wei=n-r; //右边的
int l_val=vl-1; //小值：小于vl的值个数
int m_val=vr-vl-1; //中值：大于vl、小于vr的值个数
int r_val=n-vr; //大值：大于vr的值个数，含n
//特殊情况 //r处放n
if (vr==n)
{
// cout<<"特殊情况"<<endl;
int d=1;
d *= C(l_val, l_wei); //选一些小数去左边位置
d %= mod;
d *= C(m_val, m_wei); //选一些中数去中间位置
d %= mod;
ans = d;
if (r==n) ans=0;
}
else //普遍情况
{
//cal 1 //n在r右边情况
int d1=1;
d1 *= C(l_val, l_wei); //选一些小数去左边位置
d1 %= mod;
d1 *= C(m_val, m_wei); //选一些中数去中间位置
d1 %= mod;
if (r_wei == r_val)
d1 *= qpow(2, r_val-1)-1; //防止n靠在最右边的情况
else
d1 *= qpow(2, r_val-1); //中间部分的选择情况
d1 %= mod;
//cal 2 //n在l r中间的情况
int d2=1;
d2 *= C(l_val, l_wei); //选一些小数去左边位置
d2 %= mod;
d2 *= qpow(2, r_val-1); //中间先放最大的那些数
d2 %= mod;
d2 *= C(m_val, m_wei-r_val); //选一些合格的数字来填充中间剩下的位置
d2 %= mod;
ans = d1+d2;
}
//out
ans %= mod;
cout<<ans<<endl;
return;
}
评论 (0)