当前位置:网站首页>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
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:
- A A A The length is N N N;
- 1 ≤ A i ≤ M ( 1 ≤ i ≤ N ) 1\le A_i\le M(1\le i\le N) 1≤Ai≤M(1≤i≤N)
- ∑ i = 1 N A i ≤ K \sum_{i=1}^N A_i\le K ∑i=1NAi≤K
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=x1−x1−xM 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)∗1−x1, 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)∗[xk−i]1−x1∑i=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)∗1−x1=xN(1−xM)N(1−x)−(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)=[xk−N](1−xM)N(1−x)−(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} (1−xM)N=i=0∑N(iN)(−xM)i=i=0∑N(−1)ii!(N−i)!N!xi×M
Make h ( x ) = ( 1 − x ) − ( N + 1 ) h(x)=(1-x)^{-(N+1)} h(x)=(1−x)−(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)====(1−x)−N−1(−N−1)(−1)(1−x)−N−2(−N−1)(−N−2)(−1)2(1−x)−N−3(N+1)(N+2)⋯(N+i)(1−x)−N−3===(N+1)(1−x)−N−2(N+1)(N+2)(1−x)−N−3N!(N+i)!(1−x)−N−3
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} [xk−N](1−xM)N(1−x)−(N+1)===∑i≥0(−1)ii!(N−i)!N!×N!(K−N−i×M)!(N+(K−N−i×M))!∑i≥0(−1)ii!(N−i)!N!×N!(K−N−i×M)!(N+(K−N−i×M))!∑i≥0(−1)i(K−N−i×M)!×i!(N−i)!(K−i×M)!
among i × M ≤ K − N i\times M\le K-N i×M≤K−N.
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
边栏推荐
- Dolphin scheduler configuring dataX pit records
- Es introduction learning notes
- Ora-16047 of a DG environment: dgid mismatch between destination setting and target database troubleshooting and listening vncr features
- Decentralized Collaborative Learning Framework for Next POI Recommendation
- Oracle generates millisecond timestamps
- Information: 2021 / 9 / 29 10:01 - build completed with 1 error and 0 warnings in 11S 30ms error exception handling
- sys. dbms_ scheduler. create_ Job creates scheduled tasks (more powerful and rich functions)
- Oracle告警日志alert.log和跟踪trace文件中文乱码显示
- Test on the time required for Oracle to delete data with delete
- Express ② (routage)
猜你喜欢
Express ② (routing)
Information: 2021 / 9 / 29 10:01 - build completed with 1 error and 0 warnings in 11S 30ms error exception handling
Kettle--控件解析
Detailed explanation of constraints of Oracle table
SQL learning | complex query
MySQL and PgSQL time related operations
Leetcode? The first common node of two linked lists
Solution of discarding evaluate function in surprise Library
商家案例 | 运动健康APP用户促活怎么做?做好这几点足矣
Decentralized Collaborative Learning Framework for Next POI Recommendation
随机推荐
[code analysis (4)] communication efficient learning of deep networks from decentralized data
Express middleware ③ (custom Middleware)
pycharm Install packages failed
cnpm的诡异bug
Express②(路由)
Troubleshooting of expdp export error when Oracle table has logical bad blocks
[code analysis (2)] communication efficient learning of deep networks from decentralized data
19c RAC steps for modifying VIP and scanip - same network segment
Opening: identification of double pointer instrument panel
Get the attribute value difference between two different objects with reflection and annotation
Test the time required for Oracle library to create an index with 7 million data in a common way
Detailed explanation of redis (Basic + data type + transaction + persistence + publish and subscribe + master-slave replication + sentinel + cache penetration, breakdown and avalanche)
Reading notes: fedgnn: Federated graph neural network for privacy preserving recommendation
Ora-600 encountered in Oracle environment [qkacon: fjswrwo]
Search ideas and cases of large amount of Oracle redo log
Move blog to CSDN
Port occupied 1
MySQL [acid + isolation level + redo log + undo log]
Leetcode brush question 𞓜 13 Roman numeral to integer
YARN线上动态资源调优