郑州量站站软件开发有限公司网址如何备案
首先让 n n n乘上 2 2 2。
考虑枚举最终被删除的位置有哪些。 a i = 0 a_i=0 ai=0表示这个位置被删除， a i = 1 a_i=1 ai=1表示这个位置被保留，设满足 a i = 0 a_i=0 ai=0的前缀长度为 l l l（ l l l是偶数）， p r e i pre_i prei表示 a i a_i ai的前缀和，则从左往右对于每个极长的被删除的连续段 [ l , r ] [l,r] [l,r]，其能够被删除的充要条件是：
- r − l + 1 r-l+1 r−l+1是偶数
- p r e r ≤ n − r ≤ p r e r + c n t pre_r\le n-r\le pre_r+cnt prer≤n−r≤prer+cnt
注意到式子满足单调性，因此我们只用判断除了前缀外的第一个连续段是否满足上界，以及最后一个连续段是否满足下界。
对于最后一个连续段，注意到 p r e r + n − r = n − 2 K pre_r+n-r=n-2K prer+n−r=n−2K，因此可以等价变形成 n − r ≥ n 2 − K n-r\ge \frac{n}{2}-K n−r≥2n−K，即 r ≤ n 2 + K r\le \frac{n}{2}+K r≤2n+K。这其实从另一个角度更好理解：第 i i i次操作删除的数不会超过 n 2 + i \frac{n}{2}+i 2n+i（见Alex_Wei的题解）。因此，对于 n 2 + K \frac{n}{2}+K 2n+K之后的数一定都是保留的，不会影响答案。
对于第一个连续段，发现 p r e r + c n t = l − 1 pre_r+cnt=l-1 prer+cnt=l−1，因此枚举 l l l，得到 r ≥ n − l + 1 r\ge n-l+1 r≥n−l+1，因此 [ l , n − l + 1 ] [l,n-l+1] [l,n−l+1]全部被删除，而 [ n − l + 2 , n 2 + K ] [n-l+2,\frac{n}{2}+K] [n−l+2,2n+K]只需满足连续段长度为偶数即可。
最后，我们注意到从 n n n个数中选 2 k 2k 2k个数，使得每一段为偶数的方案数为 ( n − k k ) \binom{n-k}{k} (kn−k)，因此枚举 c n t , l cnt,l cnt,l后计算组合数：
- 若 l ≤ n 2 l\le \frac{n}{2} l≤2n，则：
∑ c n t ≤ K ∑ max ( 2 c n t + 2 , n 2 − K + 1 ) ≤ l ≤ n 2 f ( K + l − n 2 − 1 , K − c n t − n 2 + l − 1 ) \sum_{cnt\le K}\sum_{\max(2cnt+2,\frac{n}{2}-K+1)\le l\le \frac{n}{2}}f(K+l-\frac{n}{2}-1,K-cnt-\frac{n}{2}+l-1) cnt≤K∑max(2cnt+2,2n−K+1)≤l≤2n∑f(K+l−2n−1,K−cnt−2n+l−1)
其中 f ( n , m ) = ( n − m m ) f(n,m)=\binom{n-m}{m} f(n,m)=(mn−m)。
- 若 l > n 2 l>\frac{n}{2} l>2n，则:
∑ c n t ≤ K f ( n 2 + K − max ( 2 c n t + 1 , n 2 ) , K − c n t ) \sum_{cnt\le K}f(\frac{n}{2}+K-\max(2cnt+1,\frac{n}{2}),K-cnt) cnt≤K∑f(2n+K−max(2cnt+1,2n),K−cnt)
对于第二部分，可以 O ( n ) O(n) O(n)计算；对于第一部分，利用 ( i + 1 j ) = ( i j ) + ( i j − 1 ) \binom{i+1}{j}=\binom{i}{j}+\binom{i}{j-1} (ji+1)=(ji)+(j−1i)可以转化为求上指标减少 1 1 1时的答案，而下指标的指针移动是 O ( 1 ) O(1) O(1)的，因此总复杂度 O ( n ) O(n) O(n)。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int mod=998244353;
const int N=2e6+5;
ll fac[N],res,sm,ifac[N];
int n,K;
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;ifac[n]=fpow(fac[n]);for(int i=n;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
ll f(int n,int m){if(n<0||m<0||n<2*m)return 0;return binom(n-m,m);
}
int l,r;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>K,n<<=1,init(n);if(K==0||n/2==K){cout<<1;return 0;}l=0,r=K-1,res=1,sm=1;for(int i=1;i<=K;i++){int nl=K-i-n/2+max(2*i+2,n/2-K+1)-1,nr=K-i-1;if(nl<=nr){while(l>nl)add(sm,binom(i-1,--l));while(r<nr)add(sm,binom(i-1,++r));while(l<nl)add(sm,-binom(i-1,l++));while(r>nr)add(sm,-binom(i-1,r--));add(sm,sm),add(sm,binom(i-1,nl-1)),add(sm,-binom(i-1,nr));add(res,sm);}add(res,f(n/2+K-max(2*i+1,n/2),K-i));}cout<<(res+mod)%mod;
}