AGC036C GP 2

由于近期集训做的一直都是校内题然后好久都怎么写题了（

发篇博客证明我还活着（其实也没人关心

好像并不是很难的一道计数就是脑子总是缺一块导致会做不出来（

首先我们可以分析性质

1.$\sum A_i = 3m$ 显然

2.$\sum A_i \&1 <= m$ 考虑我们的1 对于一个位置上有2个1我们可以将其合并看成2 所以显然不会有超过m个奇数

3.$max(A_i)<=2m$ 因为一次操作最多能使一个数+2 依旧显然

得到了3个显然的结论我们依旧不会做这个题

我们先考虑前两种限制这个比较好解决我们可以枚举奇数的个数另$F(n,m,k)$表示一共n个数和为m有不超过k个奇数

根据插板法我们可以得到柿子 $F(n,m,k)=\sum_{i=0}^{max(n,k)}C(n,i)*C((m-i)/2+n-1,n-1)$ 应该比较好理解

我们继续考虑最后一个限制可以想到>2m的数不会超过1个我们可以钦定$a_1>2m$最后乘上n即可然后让$a_1 = a_1 - 2m$

然后我们的限制就变成了前两个限制+$a_1>0$ 接着继续处理$a_1>0$

我们发现我们可以直接让$n=n-1$钦定$a_1=0$ 然后就是只考虑前两种限制了相减就好了

最后的答案就是 $F(n,3m,m)-n(F(n,m,m)-F(n-1,m,m))$

然后这里的复杂度上界其实是预处理$O(n+m)$

计数什么的还是好神仙啊。

//Love and Freedom.

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#define ll long long

#define inf 20021225

#define mdn 998244353

#define N 3000001

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch<'' || ch>'')    {if(ch=='-') f=-;ch=getchar();}

    while(ch>='' && ch<='')    s=s*+ch-'',ch=getchar();

    return f*s;

}

int fac[N],inv[N];

void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}

int ksm(int bs,int mi)

{

    int ans=;

    while(mi)

    {

        if(mi&)    ans=1ll*ans*bs%mdn;

        bs=1ll*bs*bs%mdn; mi>>=;

    }

    return ans;

}

void init(int n)

{

    fac[]=;

    for(int i=;i<=n;i++)    fac[i]=1ll*fac[i-]*i%mdn;

    inv[n]=ksm(fac[n],mdn-);

    for(int i=n;i;i--)        inv[i-]=1ll*inv[i]*i%mdn;

}

int C(int n,int m)

{

    if(n<m)    return ;

    return 1ll*fac[n]*inv[n-m]%mdn*inv[m]%mdn;

}

int F(int n,int m,int k)

{

    int top=min(n,k),ans=;

    for(int i=;i<=top;i++)    if(!((m-i)&) && m>=i)

        upd(ans,1ll*C(n,i)*C(n-+(m-i)/,n-)%mdn);

    return ans;

}

int main()

{

    int n=read(),m=read(); init(n+*m);

    int ans=F(n,m*,m)-1ll*(F(n,m,m)-F(n-,m,m)+mdn)%mdn*n%mdn;

    printf("%d\n",(ans+mdn)%mdn);

    return ;

}

AGC036C

巴特西

AGC036C GP 2

最新文章

热门文章