To_Heart—题解——「NOI国赛 Round9」划分

大概的话就是晚鸢生完的。

可能还有的问题是对形式化题意不敏感？不知道了。

题意

给定长度为 2n 的两个序列 A,B，要求构造一个长度为 2n 的序列 C， $C_i$ = $A_i$ 或 $B_i$ 。要求 C 单调不减。求 C 的方案数。

题解

因为部分分的做法对于正解并没有启发，所以就直接开始吧！

考虑分治。假设当前考虑到了区间 [l,r]。

设 dp[0/1][0/1][x] 选择 A/B[l] 和 A/B[r] 以及现在选择在 A 中选择了 x 个。

然后发现对于区间 [l,r] 通过 [l+mid],[mid+1+r] 转移的形式与多项式乘法类似，考虑多项式。发现可以把 dp[0/1][0/1] 看成是关于 x 的多项式。

剩下的就是转移。

$\sum_{j+k=i} DP[0][1](j) \times DP[1][0](k) +\sum_{j+k=i} DP[0][0](j) \times DP[0][0] (k)$

其他的转移应该类似？

但是发现自己没有处理单调的限制。发现只要判断 A/B[mid] 和 A/B[mid+1] 的单调性是否满足就好了。（也许这才是解题重点？）

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define db double
const db PI=acos(-1);
#define ll long long
#define int ll
const ll G=3,Gi=332748118; 
const ll Mod=998244353;int n,m;
ll a[4000005],b[4000005];
int r[4000005];ll Pow(ll a,ll b){ll ans=1;while(b){if(b&1) ans*=a,ans%=Mod;b>>=1,a*=a,a%=Mod;}return ans;
}void NTT(ll *a,int n,int op){for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);for(int len=1;len<n;len<<=1){ll W=Pow(op==1?G:Gi,(Mod-1)/(len<<1));for(int i=0;i<n;i+=(len<<1)){ll w=1;for(int j=0;j<len;j++,w=w*W%Mod){ll x=a[i+j],y=w*a[i+j+len]%Mod;a[i+j]=(x+y)%Mod,a[i+j+len]=(x-y+Mod)%Mod;}}}if(op==-1){ll invn=Pow(n,Mod-2);for(int i=0;i<n;i++)a[i]=a[i]*invn%Mod;}
}void Solve(int l,int r,ll *dp00,ll *dp01,ll *dp10,ll *dp11){if(l==r) return dp00[0]=1,dp11[1]=1,void();int mid=(l+r)>>1;int len=(r-l+1);int Max=1,qwq=0;while(Max<len+1) Max<<=1,qwq++;ll l_dp00[Max],l_dp01[Max],l_dp10[Max],l_dp11[Max];ll r_dp00[Max],r_dp01[Max],r_dp10[Max],r_dp11[Max];memset(l_dp00,0,sizeof l_dp00);memset(l_dp01,0,sizeof l_dp01);memset(l_dp10,0,sizeof l_dp10);memset(l_dp11,0,sizeof l_dp11);memset(r_dp00,0,sizeof r_dp00);memset(r_dp01,0,sizeof r_dp01);memset(r_dp10,0,sizeof r_dp10);memset(r_dp11,0,sizeof r_dp11);Solve(l,mid,l_dp00,l_dp01,l_dp10,l_dp11);Solve(mid+1,r,r_dp00,r_dp01,r_dp10,r_dp11);for(int i=0;i<Max;i++) ::r[i]=(::r[i>>1]>>1)|((i&1)<<(qwq-1));NTT(l_dp00,Max,1);NTT(l_dp01,Max,1);NTT(l_dp10,Max,1);NTT(l_dp11,Max,1);NTT(r_dp00,Max,1);NTT(r_dp01,Max,1);NTT(r_dp10,Max,1);NTT(r_dp11,Max,1);if(a[mid]<=a[mid+1]){for(int i=0;i<Max;i++) dp00[i]+=l_dp00[i]*r_dp00[i]%Mod,dp00[i]%=Mod,dp11[i]+=l_dp10[i]*r_dp01[i]%Mod,dp11[i]%=Mod,dp01[i]+=l_dp00[i]*r_dp01[i]%Mod,dp01[i]%=Mod,dp10[i]+=l_dp10[i]*r_dp00[i]%Mod,dp10[i]%=Mod;}if(a[mid]<=b[mid+1]){for(int i=0;i<Max;i++) dp00[i]+=l_dp00[i]*r_dp10[i]%Mod,dp00[i]%=Mod,dp11[i]+=l_dp10[i]*r_dp11[i]%Mod,dp11[i]%=Mod,dp01[i]+=l_dp00[i]*r_dp11[i]%Mod,dp01[i]%=Mod,dp10[i]+=l_dp10[i]*r_dp10[i]%Mod,dp10[i]%=Mod;}if(b[mid]<=a[mid+1]){for(int i=0;i<Max;i++) dp00[i]+=l_dp01[i]*r_dp00[i]%Mod,dp00[i]%=Mod,dp11[i]+=l_dp11[i]*r_dp01[i]%Mod,dp11[i]%=Mod,dp01[i]+=l_dp01[i]*r_dp01[i]%Mod,dp01[i]%=Mod,dp10[i]+=l_dp11[i]*r_dp00[i]%Mod,dp10[i]%=Mod;}if(b[mid]<=b[mid+1]){for(int i=0;i<Max;i++) dp00[i]+=l_dp01[i]*r_dp10[i]%Mod,dp00[i]%=Mod,dp11[i]+=l_dp11[i]*r_dp11[i]%Mod,dp11[i]%=Mod,dp01[i]+=l_dp01[i]*r_dp11[i]%Mod,dp01[i]%=Mod,dp10[i]+=l_dp11[i]*r_dp10[i]%Mod,dp10[i]%=Mod;}NTT(dp00,Max,-1);NTT(dp01,Max,-1);NTT(dp10,Max,-1);NTT(dp11,Max,-1);
}int sub;
ll DP00[2000005],DP11[2000005],DP01[2000005],DP10[2000005];signed main(){freopen("divide.in","r",stdin);freopen("divide.out","w",stdout);cin>>n>>sub;for(int i=1;i<=2*n;i++) scanf("%lld",&a[i]);for(int i=1;i<=2*n;i++) scanf("%lld",&b[i]);Solve(1,n*2,DP00,DP01,DP10,DP11);printf("%lld\n",(DP00[n]+DP01[n]+DP10[n]+DP11[n])%Mod);
}

总结一下就是：