D. Monocarp and the Set
题目大意,给你一个表示排列元素的序列,包括 <?>
, 其中 <
表示在之前是最小的 >
表示在之前是最大的,否则就是 ?
,有 m 次操作 ,每次可能修改下标的值,你这个表示序列的序列最多能表示多少种排列。
先不考虑修改,对于最初始的序列,第一个绝对不能是问号,然后从后往前看,如果不是问号就只能填一种东西,是问号可以填 x−2 (假设当前下标为 x ) 个数。以此可以统计答案。
修改也同理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=300300; const int modp=998244353;
int n,m,a[maxn];
int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%modp; x=x*x%modp; y>>=1; } return ans; }
void solve() { cin>>n>>m; int ans=1; for(int i=1;i<n;i++) { char tmp; cin>>tmp; if(tmp=='?') a[i]=1; else a[i]=0; } for(int i=n-1;i>1;i--) { if(a[i]) ans=(1ll*ans*(i-1))%modp; } if(a[1]) cout<<0<<'\n'; else cout<<ans<<'\n'; for(int i=1;i<=m;i++) { int x; char tmp; cin>>x>>tmp; int tans=ans; int looker=(tmp=='?'); if(x!=1) { if(looker&&!a[x]) tans=tans*(x-1)%modp; else if(!looker&&a[x]) tans=tans*ksm((x-1),modp-2)%modp; } a[x]=(tmp=='?'); ans=tans; if(a[1]) cout<<0<<'\n'; else cout<<tans<<'\n'; } }
signed main() { ios::sync_with_stdio(false); int T=1;
while(T--) { solve(); } return 0; }
|