欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

jzoj5828 [省选模拟2018.8.18]⽔果拼盘 乱搞

程序员文章站 2024-02-12 22:46:10
...

Description


好长啊
jzoj5828 [省选模拟2018.8.18]⽔果拼盘 乱搞
jzoj5828 [省选模拟2018.8.18]⽔果拼盘 乱搞

Solution


正解是fwt一类的东西,好像还要生成函数。我的这种做法是乱搞得来的
考虑到期望的线性性,我们只需要考虑每个ai的和bi各自的贡献即可
我们记n个水果拼盘中第i个出现的次数为toti,那么ai的系数显然为(nk)(ntotik)(nk)bi的系数就是1-ai的系数
然后预处理一波阶乘和逆元就行了

Code


#include <stdio.h>
#include <string.h>
#include <bitset>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

typedef long long LL;
const int MOD=998244353;
const int N=1100005;

int a[N],b[N],tot[N],n,m,k;

LL fac[N],inv[N],ans;

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

LL ksm(LL x,LL dep) {
    LL ret=1;
    for (;dep;) {
        if (dep&1) ret=ret*x%MOD;
        x=x*x%MOD; dep>>=1;
    }
    return ret;
}

LL C(int n,int m) {
    if (n<m) return 0;
    if (n==m) return 1;
    LL ret=fac[n]*inv[m]%MOD;
    ret=ret*inv[n-m]%MOD;
    return ret;
}

int main(void) {
    freopen("data.in","r",stdin);
    freopen("myp.out","w",stdout);
    n=read(),m=read(),k=read();
    fac[0]=1; rep(i,1,n) fac[i]=1LL*i*fac[i-1]%MOD;
    inv[n]=ksm(fac[n],MOD-2); drp(i,n-1,1) inv[i]=1LL*(i+1)*inv[i+1]%MOD;
    rep(i,1,m) a[i]=read();
    rep(i,1,m) b[i]=read();
    rep(i,1,n) {
        int s=read(),x;
        for (;s--;) {
            x=read();
            tot[x]++;
        }
    }
    rep(i,1,m) {
        LL tmp1=C(n,k);
        LL tmp2=C(n-tot[i],k);
        LL tmp3=(tmp1-tmp2+MOD)%MOD;
        ans=(ans+1LL*a[i]*tmp3%MOD*ksm(tmp1,MOD-2)%MOD)%MOD;
        ans=(ans+1LL*b[i]*tmp2%MOD*ksm(tmp1,MOD-2)%MOD)%MOD;
    }
    printf("%lld\n", ans);
    return 0;
}
相关标签: jzoj