「题解」Count

(未完待续)

题目链接:GMOJ 6300

题目

题目描述

给定两个整数 $n,m$,求 $k$ 元组 $(a _ 1,a _ 2,\cdots,a _ k)$ 的个数,满足 $\sum^k _ {i=1}a _ i=n$,且 $a _ 1,a _ 2,\cdots,a _ k$ 均不是 $m$ 的倍数。

输入格式

共一行,三个正整数 $n,m,k$。

输出格式

共一行,为 $k$ 元组的个数,答案对 $998244353$ 取模。

样例输入输出

#1

  • Input:
5 3 3
  • Output:
3

样例解释

#1

满足条件的三元组为:$(1,2,2),(2,1,2),(2,2,1)$。

数据范围

对于 $30\%$ 的数据,$n\leq 2000,k\leq 3$。
对于 $50\%$ 的数据,$n\leq 10^{18},m\leq 2000,k\leq 3$ 。
对于 $70\%$ 的数据,$n\leq 10^{18},m\leq 5000,k\leq 20$ 。
对于 $100\%$ 的数据,$n\leq 10^{18},m\leq 5000,k\leq 2000$ 。

时空限制

$$1\text{s}/512\text{MiB}$$

题解

本题有多种解法(直接模拟(10~30分),50 分做法(我不会),70 分做法(比正解还难),数论解法(100分))。

解法 A (直接模拟)

思路

思路十分显然,无需过多的说明,预计得分 10~30 分。

代码

代码等会再放。

解法 B (我不会)

预计得分 50 分。

解法 C (我不会)

预计得分 70 分。

解法 D (数论正解)

思路

等会再放

代码

先贴个代码。

#include<cstdio>
typedef long long ll;
#define mod 998244353
const int MAXN=10000000+5;
ll n,m,k,inv[MAXN];
int fac[MAXN],fac_inv[MAXN];
void Init(void);
ll C(ll,ll);
int main(void){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    register ll i,ans=0,A,opt,res;
    Init();
    scanf("%lld%lld%lld",&n,&m,&k);
    for(A=n%m;A<=k*(m-1);A+=m){
        opt=1,res=0;
        for(i=0;i<=k&&i*(m-1)<=A;++i){
            res=(res+opt*C(A-i*(m-1)-1,k-1)%mod*C(k,i)%mod+mod)%mod;
            opt=-opt;//容斥系数是-1的i次方
        }
        ans=(ans+res*C(k+(n-A)/m-1,k-1)%mod+mod)%mod;
    }
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void Init(void){
    register int i;
    inv[1]=1;
    for(i=2;i<MAXN;++i)//线性求逆元
        inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    fac[0]=fac_inv[0]=1;
    for(i=1;i<MAXN;++i){//递推求阶乘及其逆元
        fac[i]=(ll)fac[i-1]*i%mod;
        fac_inv[i]=(ll)fac_inv[i-1]*inv[i]%mod;
    }
    return;
}
ll C(ll n,ll m){//求组合数
    if(n<m)
        return 0;
    if(n<MAXN&&m<MAXN)
        return (ll)fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;
    register ll i,res=1;
    for(i=1;i<=m;++i)
        res=res*inv[i]%mod*((n-m+i)%mod)%mod;
    return res;
}