传送门

---

Div 2的比赛，前四题还有那么多人过，应该是SB题，就不讲了。

这场比赛一堆计数题，很舒服。（虽然我没打）

E. The Top Scorer

其实这题也不难，不知道为什么这么少人过。

考虑枚举那人的分数和有多少人和他同分，推一下就会发现我们只需要知道\(calc(sum,n,top)\)表示\(sum\)分，分给\(n\)个人，分数小于\(top\)，的方案数。

好像不是很好直接搞，考虑容斥，枚举一下至少有几个人不满足条件即可。

#include<bits/stdc++.h>

namespace my_std{

    using namespace std;

    #define pii pair<int,int>

    #define fir first

    #define sec second

    #define MP make_pair

    #define rep(i,x,y) for (int i=(x);i<=(y);i++)

    #define drep(i,x,y) for (int i=(x);i>=(y);i--)

    #define go(x) for (int i=head[x];i;i=edge[i].nxt)

    #define mod (ll(998244353))

    #define sz 10101

    typedef long long ll;

    typedef double db;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    template<typename T>inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}

    template<typename T>inline void read(T& t)

    {

        t=0;char f=0,ch=getchar();double d=0.1;

        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}

        t=(f?-t:t);

    }

    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}

    void file()

    {

        #ifndef ONLINE_JUDGE

        freopen("a.txt","r",stdin);

        #endif

    }

    #ifdef mod

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}

    ll inv(ll x){return ksm(x,mod-2);}

    #else

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}

    #endif

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

ll fac[sz],_fac[sz];

void init(){fac[0]=_fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}

ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int n,r,s;

ll calc(int sum,int n,int top) // sum points for n people , < top

{

    if (!n) return sum==0;

    ll ret=0;

    rep(i,0,n)

    {

        if (i*top>sum) return ret;

        int cur=sum-i*top;

        ret=(ret+1ll*((i&1)?-1:1)*C(cur+n-1,n-1)*C(n,i)%mod+mod)%mod;

    }

    return ret;

}

int main()

{

    file();

    init();

    read(n,s,r);

    ll tot=C(s-r+n-1,n-1);

    ll ans=0;

    rep(i,r,s)

    {

        rep(j,0,n-1)

        {

            int rest=s-i-i*j;if (rest<0) break;

            ans=(ans+calc(rest,n-j-1,i)*C(n-1,j)%mod*inv(j+1)%mod)%mod;

        }

    }

    cout<<ans*inv(tot)%mod;

    return 0;

}

---

F. Inversion Expectation

很容易想到把各个部分的贡献拆开来算。

分成三个部分：已知对已知、未知对未知、未知对已知。

前两个都很好搞，第三个考虑期望的线性性（虽然我不知道那是啥），随便搞搞就好了。

#include<bits/stdc++.h>

clock_t t=clock();

namespace my_std{

    using namespace std;

    #define pii pair<int,int>

    #define fir first

    #define sec second

    #define MP make_pair

    #define rep(i,x,y) for (int i=(x);i<=(y);i++)

    #define drep(i,x,y) for (int i=(x);i>=(y);i--)

    #define go(x) for (int i=head[x];i;i=edge[i].nxt)

    #define templ template<typename T>

    #define mod 998244353ll

    #define sz 200220

    typedef long long ll;

    typedef double db;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}

    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}

    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}

    templ inline void read(T& t)

    {

        t=0;char f=0,ch=getchar();double d=0.1;

        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}

        t=(f?-t:t);

    }

    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}

    void file()

    {

        #ifndef ONLINE_JUDGE

        freopen("a.in","r",stdin);

        #endif

    }

    inline void chktime()

    {

        #ifndef ONLINE_JUDGE

        cout<<(clock()-t)/1000.0<<'\n';

        #endif

    }

    #ifdef mod

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}

    ll inv(ll x){return ksm(x,mod-2);}

    #else

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}

    #endif

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

int n,m;

int a[sz];

bool vis[sz];

ll tr[sz];

void add(int x,int y){while (x<=n) (tr[x]+=y)%=mod,x+=(x&(-x));}

int query(int x){ll ret=0;while (x) (ret+=tr[x])%=mod,x-=(x&(-x));return ret;}

ll fac[sz];

int main()

{

    file();

    cin>>n;

    rep(i,1,n)

    {

        cin>>a[i];

        if (a[i]==-1) ++m;

    }

    ll ans=0;

    rep(i,1,n) if (a[i]!=-1) (ans+=query(n)-query(a[i]))%=mod,add(a[i],1);

    fac[0]=1;rep(i,1,n) fac[i]=fac[i-1]*i%mod;

    (ans*=fac[m])%=mod;

    (ans+=fac[m]*inv(4)%mod*(1ll*m*(m-1)%mod)%mod)%=mod;

    int cnt=0;

    rep(i,1,n)

        if (a[i]!=-1) (ans+=fac[m-1]*(1ll*cnt*(m+query(a[i])-a[i])%mod+1ll*(m-cnt)*(a[i]-query(a[i]))%mod)%mod)%=mod;

        else ++cnt;

    cout<<ans*inv(fac[cnt])%mod;

    return 0;

}

---

G. Lucky Tickets

很容易想到枚举两边有多少分。

考虑一个DP：\(dp_{i,j}\)表示前\(i\)位的和为\(j\)的方案数，转移方程显然。

感受一下，这东西就是一个多项式快速幂，就做完了。

#include<bits/stdc++.h>

clock_t t=clock();

namespace my_std{

    using namespace std;

    #define pii pair<int,int>

    #define fir first

    #define sec second

    #define MP make_pair

    #define rep(i,x,y) for (int i=(x);i<=(y);i++)

    #define drep(i,x,y) for (int i=(x);i>=(y);i--)

    #define go(x) for (int i=head[x];i;i=edge[i].nxt)

    #define templ template<typename T>

    #define sz 8010100

    #define mod 998244353ll

    typedef long long ll;

    typedef double db;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}

    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}

    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}

    templ inline void read(T& t)

    {

        t=0;char f=0,ch=getchar();double d=0.1;

        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}

        t=(f?-t:t);

    }

    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}

    void file()

    {

        #ifndef ONLINE_JUDGE

        freopen("a.in","r",stdin);

        #endif

    }

    inline void chktime()

    {

        #ifndef ONLINE_JUDGE

        cout<<(clock()-t)/1000.0<<'\n';

        #endif

    }

    #ifdef mod

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}

    ll inv(ll x){return ksm(x,mod-2);}

    #else

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}

    #endif

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

int limit,r[sz];

void NTT_init(int n)

{

    limit=1;int l=-1;

    while (limit<=n+n) limit<<=1,++l;

    rep(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l);

}

void NTT(ll *a,int type)

{

    rep(i,0,limit-1) if (i<r[i]) swap(a[i],a[r[i]]);

    rep(i,0,limit-1) a[i]%=mod;

    for (int mid=1;mid<limit;mid<<=1)

    {

        ll Wn=ksm(3,(mod-1)/mid>>1);if (type==-1) Wn=inv(Wn);

        for (int j=0,len=mid<<1;j<limit;j+=len)

        {

            ll w=1;

            for (int k=0;k<mid;k++,w=w*Wn%mod)

            {

                ll x=a[j+k],y=a[j+k+mid]*w;

                a[j+k]=(x+y)%mod;a[j+k+mid]=(1ll*mod*mod-y+x)%mod;

            }

        }

    }

    if (type==1) return;

    ll I=inv(limit);

    rep(i,0,limit-1) a[i]=a[i]*I%mod;

}

int n,K;

ll a[sz];

int main()

{

    file();

    read(n,K);

    int x;

    rep(i,1,K) read(x),a[x]=1;

    NTT_init(n*10);

    NTT(a,1);

    rep(i,0,limit) a[i]=ksm(a[i],n/2);

    NTT(a,-1);

    ll ans=0;

    rep(i,0,n*10) (ans+=a[i]*a[i]%mod)%=mod;

    cout<<ans;

    return 0;

}