当前位置:网站首页>Atcoder beginer contest 248c dice sum (generating function)

Atcoder beginer contest 248c dice sum (generating function)

2022-04-23 13:53:00 MoYan1082

AtCoder Beginner Contest 248C Dice Sum

Topic link

The question

Given three integers N , M , K N,M,K N,M,K, Find how many sequences meet the following conditions A A A

  1. A A A The length is N N N;
  2. 1 ≤ A i ≤ M ( 1 ≤ i ≤ N ) 1\le A_i\le M(1\le i\le N) 1AiM(1iN)
  3. ∑ i = 1 N A i ≤ K \sum_{i=1}^N A_i\le K i=1NAiK

The final result is right 998244353 modulus .

Ideas

For each of these A i A_i Ai, It can be used f ( x ) = 0 + x + x 2 + . . . + x M = x 1 − x M 1 − x f(x)=0+x+x^2+...+x^M=x\frac{1-x^M}{1-x} f(x)=0+x+x2+...+xM=x1x1xM To express .

Make F ( x ) = f ( x ) N F(x)=f(x)^N F(x)=f(x)N, So the result is ∑ i = 0 k [ x i ] F ( x ) \sum_{i=0}^k [x^i]F(x) i=0k[xi]F(x).

Make G ( x ) = F ( x ) ∗ ( 1 + x + x 2 + . . . ) = F ( x ) ∗ 1 1 − x G(x)=F(x)*(1+x+x^2+...)=F(x)*\frac{1}{1-x} G(x)=F(x)(1+x+x2+...)=F(x)1x1, be
[ x k ] G ( x ) = ∑ i = 0 k [ x k ] F ( x ) ∗ [ x k − i ] 1 1 − x = ∑ i = 0 k [ x k ] F ( x ) \begin{matrix} [x^k]G(x)&=&\sum_{i=0}^{k}[x^k]F(x)*[x^{k-i}]\frac{1}{1-x} \\ \\ &=&\sum_{i=0}^k[x^k]F(x) \end{matrix} [xk]G(x)==i=0k[xk]F(x)[xki]1x1i=0k[xk]F(x)

Because of :
G ( x ) = F ( x ) ∗ 1 1 − x = x N ( 1 − x M ) N ( 1 − x ) − ( N + 1 ) G(x)=F(x)*\frac{1}{1-x}=x^N(1-x^M)^N(1-x)^{-(N+1)} G(x)=F(x)1x1=xN(1xM)N(1x)(N+1)

so : [ x k ] G ( x ) = [ x k − N ] ( 1 − x M ) N ( 1 − x ) − ( N + 1 ) [x^k]G(x)=[x^{k-N}](1-x^M)^N(1-x)^{-(N+1)} [xk]G(x)=[xkN](1xM)N(1x)(N+1).

among
( 1 − x M ) N = ∑ i = 0 N ( N i ) ( − x M ) i = ∑ i = 0 N ( − 1 ) i N ! i ! ( N − i ) ! x i × M (1-x^M)^N=\sum_{i=0}^N\binom{N}{i}(-x^M)^i=\sum_{i=0}^N(-1)^i\frac{N!}{i!(N-i)!}x^{i\times M} (1xM)N=i=0N(iN)(xM)i=i=0N(1)ii!(Ni)!N!xi×M

Make h ( x ) = ( 1 − x ) − ( N + 1 ) h(x)=(1-x)^{-(N+1)} h(x)=(1x)(N+1), be :
h ( x ) = ( 1 − x ) − N − 1 h ′ ( x ) = ( − N − 1 ) ( − 1 ) ( 1 − x ) − N − 2 = ( N + 1 ) ( 1 − x ) − N − 2 h ′ ′ ( x ) = ( − N − 1 ) ( − N − 2 ) ( − 1 ) 2 ( 1 − x ) − N − 3 = ( N + 1 ) ( N + 2 ) ( 1 − x ) − N − 3 ⋯ h ( i ) ( x ) = ( N + 1 ) ( N + 2 ) ⋯ ( N + i ) ( 1 − x ) − N − 3 = ( N + i ) ! N ! ( 1 − x ) − N − 3 \begin{matrix} h(x)&=&(1-x)^{-N-1}\\ \\ h'(x)&=&(-N-1)(-1)(1-x)^{-N-2}&=&(N+1)(1-x)^{-N-2} \\ \\ h''(x)&=&(-N-1)(-N-2)(-1)^2(1-x)^{-N-3}&=&(N+1)(N+2)(1-x)^{-N-3} \\ \\ \cdots \\ \\ h^{(i)}(x)&=&(N+1)(N+2)\cdots (N+i)(1-x)^{-N-3} &=& \frac{(N+i)!}{N!} (1-x)^{-N-3} \\ \\ \end{matrix} h(x)h(x)h(x)h(i)(x)====(1x)N1(N1)(1)(1x)N2(N1)(N2)(1)2(1x)N3(N+1)(N+2)(N+i)(1x)N3===(N+1)(1x)N2(N+1)(N+2)(1x)N3N!(N+i)!(1x)N3

By Taylor's formula , have to :
h ( x ) = h ( 0 ) + h ′ ( 0 ) x 1 ! + h ′ ′ ( 0 ) x 2 2 ! + . . . + h ( n ) ( 0 ) x n n ! + . . . h(x)=h(0)+\frac{h'(0)x}{1!}+\frac{h''(0)x^2}{2!}+...+\frac{h^{(n)}(0)x^n}{n!}+... h(x)=h(0)+1!h(0)x+2!h(0)x2+...+n!h(n)(0)xn+...

[ x i ] h ( x ) = h ( i ) ( 0 ) i ! x i = ( N + i ) ! N ! i ! x i [x^i]h(x)=\frac{h^{(i)}(0)}{i!}x^i=\frac{(N+i)!}{N!i!}x^i [xi]h(x)=i!h(i)(0)xi=N!i!(N+i)!xi

The result is :
[ x k − N ] ( 1 − x M ) N ( 1 − x ) − ( N + 1 ) = ∑ i ≥ 0 ( − 1 ) i N ! i ! ( N − i ) ! × ( N + ( K − N − i × M ) ) ! N ! ( K − N − i × M ) ! = ∑ i ≥ 0 ( − 1 ) i N ! i ! ( N − i ) ! × ( N + ( K − N − i × M ) ) ! N ! ( K − N − i × M ) ! = ∑ i ≥ 0 ( − 1 ) i ( K − i × M ) ! ( K − N − i × M ) ! × i ! ( N − i ) ! \begin{matrix} [x^{k-N}](1-x^M)^N(1-x)^{-(N+1)} &=&\sum_{i\ge0}(-1)^i\frac{N!}{i!(N-i)!}\times \frac{(N+(K-N-i\times M))!}{N!(K-N-i\times M)!} \\ \\ &=&\sum_{i\ge0}(-1)^i\frac{N!}{i!(N-i)!}\times \frac{(N+(K-N-i\times M))!}{N!(K-N-i\times M)!} \\ \\ &=&\sum_{i\ge0}(-1)^i\frac{(K-i\times M)!}{(K-N-i\times M)!\times i!(N-i)!} \\ \\ \end{matrix} [xkN](1xM)N(1x)(N+1)===i0(1)ii!(Ni)!N!×N!(KNi×M)!(N+(KNi×M))!i0(1)ii!(Ni)!N!×N!(KNi×M)!(N+(KNi×M))!i0(1)i(KNi×M)!×i!(Ni)!(Ki×M)!

among i × M ≤ K − N i\times M\le K-N i×MKN.

AC Code for

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
const int N = 1e6 + 10;

ll fac[N], n, m, k;
ll power(ll a, ll b) {
    
    ll res = 1;
    while (b) {
    
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll x) {
     return power(x, mod - 2); }

void init() {
    
    fac[0] = 1;
    for (int i = 1; i <= N - 10; i++) fac[i] = fac[i - 1] * i % mod;
}

int main() {
    
    init();
    cin >> n >> m >> k;
    ll res = 0;
    for (int i = 0;; i++) {
    
        if (i * m > k - n) break;
        ll tmp = fac[k - i * m] * inv(fac[i]) % mod * inv(fac[n - i]) % mod *
                 inv(fac[k - n - i * m]) % mod;

        res = ((res + (i % 2 ? -1 : 1) * tmp) % mod + mod) % mod;
    }
    cout << res;

    return 0;
}

版权声明
本文为[MoYan1082]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231350393859.html