智慧t2，我不智慧，赛时想到了一点点。。
题意：
给一个单调不降的序列 \(a_1,a_2,...,a_n\) 。 给定一个整数 \(x\)。求一个 \(b\) 序列使得 任意 \(\forall i(1<i\le n) \ a_i-b_i<a_{i+1}-b_{i+1}\) 且 \(\forall i<j<x\ \ b_i\le b_j.\forall x<j<i\ \ b_i\le b_j\)。
做法：
整理一下 设最后的 \(a_i-b_i\) 序列为 \(c\) .
当 \(1\le i<x:\)
\[a_i\le a_{i+1}\\ b_i\le b_{i+1}\\ c_i\le c_{i+1}\\ \\ a_i-c_i\le a_{i+1}-c_{i+1}\\ c_i-a_i\ge c_{i+1}-a_{i+1}\\ c_i+a_{i+1}-a_{i}\ge c_{i+1}\\ c_i\le c_{i+1}\le c_i+a_{i+1}-a_{i} \]所以 取值范围有 \(a_{i+1}-a_i+1\) 种。直接 prod 起来就好。
当 \(x<i\le n\) :
也就是要求 \(x\) 右侧的不降序列，再减去一个不增序列，仍然是一个不降序列，且要求最终序列第一个元素不小于 \(a_x\)。
不难发现，在这种情况下，如果最终序列第一个元素不小于 \(a_x\) 的要求被满足，后面的元素依然还是不降的（后面更大的元素，减去了一个更小的数，显然还是不会比你小）。 令 \(len=n-x\) \(y=a_{x+1}-a_x\) ，那么问题变成了数长度为 \(len\)，值域在 \([0,d]\) 的序列个数。
插板法一下 ，答案就是 \(\binom{y+len}{len}\).
然后两边乘起来。
最终答案就是
\[\binom{a_{x+1}-a_x+n-x}{n-x}\prod_{i=1}^{x-1}(a_{i}-a_{i-1}+1) \]妙妙妙妙米奇妙妙屋
代码：
直接放std了。懒得写。对不起。
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,a[300005],x;
int qpow(int a,int b)
{
if(b==0) return 1;
int g=qpow(a,b/2);
g=1ll*g*g%mod;
if(b&1) g=1ll*g*a%mod;
return g;
}
int solvel()
{
int ans=1;
for(int i=1;i<x;i++)
{
ans=1ll*ans*(a[i]-a[i-1]+1)%mod;
}
return ans;
}
int solver()
{
if(x==n) return 1;
int d=a[x+1]-a[x],ans=1,len=n-x;
//C(d+len,len)
for(int i=len,j=d+len;i>=1;i--,j--)
{
ans=1ll*ans*qpow(i,mod-2)%mod*j%mod;
}
return ans;
}
int main()
{
freopen("fate.in","r",stdin);
freopen("fate.out","w",stdout);
assert(cin>>n);
for(int i=1;i<=n;i++)
{
assert(cin>>a[i]);
}
assert(cin>>x);
cout<<1ll*solvel()*solver()%mod;
assert(!(cin>>x));
}
这个马蜂i dont like
标签：le,fate,int,len,1127noip,序列,模拟,mod From： https://www.cnblogs.com/slayer-wt/p/18572917