Topic description

Given \ (n \) variables, each variable has \ (a_i \), and the value of each variable is \ ([1,b_i] \). For each scheme, record \ (S \) as its sum, and then assign \ (S \) to \ (m \) variables with the initial value of \ (0 \). It is necessary to ensure that each variable is greater than \ (0 \), and calculate the number of schemes. The answer is to mold \ (998244353 \).

\(n\times m\le 10^5,a_i\le 10^5,b_i\in [1,998244352]\)

\(\rm Sol:\)

It's probably the practice of the rabbit team. This question is too fairy. I worship the rabbit team directly.

For a \ (S \), the answer is divided into two parts. The first part is the number of schemes to get \ (S \), and the second is the number of schemes to allocate \ (S \).

For the second part, it is not difficult to get the answer of the column generation function as \ (\ frac{1}{(1-x)^m}[x^{S-m}]=\binom{S-1}{m-1} \)

Set \ (G \) as the generating function of the first part of the answer, then the answer is:

For convenience, let \ (m=m-1 \), so the answer can be written as:

Namely:

This is to note that \ (G(x) \) has no constant term because each subfunction is \ (x+x^2 +... \)

Considering the \ (m \) derivative of \ (f(x)=a\times x^k \), the result is \ (k^{\underline{m}}\times a\times x^{k-m} \), so it is not difficult to find the answer, that is \ (\ frac{1}{m!}\times G^{(m)}(1)\)

Next, get a generating function for each \ (I \) column and set \ (F(x)=\prod f_i(x)^{a_i} \), then consider \ (F^{(m)}(x) \), where \ (f_0(x)=\frac{1}{x} \)

• According to the multiplication rule \ ((f\cdot g)'=f'g+fg' \)
• Considering the continuous use of the multiplication rule, it is observed that \ ((f\cdot g\cdot h)'=f'gh+fg'h+fgh' \), it is not difficult to find that the multiplication rule does not take effect after it takes effect once, or peel it from the outermost layer?
• In essence, the multiplication rule is similar to the 01 knapsack model. When a \ (i \) is derived once, other elements do not need additional derivation. Combined with the addition rule, it is not difficult to see that the derivation of \ (m \) by continuous multiplication can be regarded as such a process:
• Select an element \ (f \) in each round and derive it once. For all schemes, the derived \ (f \) sequences are multiplied and then added.
• So there is \ (F^{(m)}(x)=\sum_{c_1,c_2...c_n} \frac{m!}{c_1!c_2!...c_n!}[c_1+c_2+...+c_n=m] \prod f_i^{(c_i)}\)
• It can also be understood from the perspective of generating function. Add an auxiliary variable \ (z \), and the answer is:

In this way, we can consider getting a generating function with a length of \ (\ mathcal O(m) \) for each \ (I \) column, and then calculating the convolution sum of its \ (a_i \) power.

Our only problem is to calculate \ (f_i^c(1) \), which is not difficult to note:

For \ (c=0 \), there is \ (f_i^{(0)}(1)=b_i\)

For \ (c=k \), there is \ (f_i^{(k)}(1)=\sum_{j\ge k}^m j^{\underline{k}}\)

So the calculated sum is essentially \ (\ sum {UJ = 1} ^ {m} J ^ {\ underline {K} \). For \ (k\ge 1 \), note that \ (J ^ {\ underline {K}} = \ frac {(j + 1) ^ {\ underline {K + 1}} - J ^ {\ underline {K + 1}} {K + 1} \)

So \ (\ sum {J = 1} ^ {B _i} J ^ {\ underline {K}} = \ frac {1} {K + 1} \ sum {J = 1} ^ m (j + 1) ^ {\ underline {K + 1}} - J ^ {\ underline {K + 1}} = \ frac {(B _i + 1) ^ {\ underline K + 1}} \)

For \ (i=0 \), \ (f(x)=\frac{1}{x} \), so \ (f ^ {(k)} (x) = (- 1) ^ k! \), So \ (\ frac{f^{(k)}(1)}{k!}=(-1)^K \), so do \ (n \) times convolution, and each time \ (\ mathcal O(m\log m) \) is processed, depending on whether the fast power is written \ (\ exp \ & \ ln \), the complexity is \ (\ mathcal O(nm\log m)/O(nm\log m\log a) \)

So the fairy problem was finished.

\(Code:\)

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int P = 998244353 ; 
const int Gi = 332748118 ;
const int G = 3 ; 
const int N = 6e5 + 5 ;
int n, m, limit, Inv, L, iv[N], inv[N], A[N], B[N], f[N], R[N], Ans[N] ; 
int fpow(int x, int k) {
	int ans = 1, base = x ; 
	while(k) {
		if(k & 1) ans = ans * base % P ; 
		base = base * base % P, k >>= 1 ;  
	} return ans ; 
}
void init(int x) {
	limit = 1, L = 0 ; while( limit < x ) limit <<= 1, ++ L ; 
	for(re int i = 0; i < limit; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)) ; 
	Inv = fpow( limit, P - 2 ) ; 
}
void NTT(int *a, int type) {
	for(re int i = 0; i < limit; ++ i) if(R[i] > i) swap(a[i], a[R[i]]) ;
	for(re int k = 1; k < limit; k <<= 1 ) {
		int d = fpow((type == 1) ? G : Gi, (P - 1) / (k << 1) ) ;
		for(re int i = 0; i < limit; i += (k << 1) )
		for(re int j = i, g = 1; j < i + k; ++ j, g = g * d % P ) {
			int nx = a[j], ny = a[j + k] * g % P ; 
			a[j] = (nx + ny) % P, a[j + k] = (nx - ny + P) % P ; 
		}
	} if( !type ) rep( i, 0, limit ) a[i] = a[i] * Inv % P ; 
}
int _Hx[N], _Base[N], Base[N] ; 
void Fpow(int k) {
	_Hx[0] = 1 ; rep( i, 0, m ) Base[i] = f[i] ;
	while(k) {
		rep( i, 0, m ) _Base[i] = Base[i] ; NTT(_Base, 1) ; 
		if(k & 1) {
			NTT(_Hx, 1) ; rep( i, 0, limit ) _Hx[i] = _Hx[i] * _Base[i] % P ; 
			NTT(_Hx, 0) ; rep( i, m + 1, limit ) _Hx[i] = 0 ; 
		}
		rep( i, 0, limit ) _Base[i] = _Base[i] * _Base[i] % P ; 
		NTT(_Base, 0) ;
		rep( i, 0, m ) Base[i] = _Base[i] ; 
		rep( i, 0, limit ) _Base[i] = 0 ; k >>= 1 ; 
	}
	rep( i, 0, m ) f[i] = _Hx[i] ; 
	rep( i, 0, limit ) Base[i] = _Base[i] = _Hx[i] = 0 ; 
}
signed main()
{
	m = gi() - 1, n = gi() ; 
	rep( i, 1, n ) A[i] = gi(), B[i] = gi() ; inv[0] = iv[0] = 1 ; 
	rep( i, 1, m + 10 ) 
		iv[i] = fpow( i, P - 2 ), inv[i] = inv[i - 1] * iv[i] % P ; 
	init(m + m + 5) ;
	rep( i, 0, m ) Ans[i] = (i & 1) ? P - 1 : 1 ;
	rep( i, 1, n ) {
		f[0] = B[i] ; int t = (B[i] + 1) % P ; 
		rep( k, 1, m ) 
			t = t * (B[i] - k + 1) % P, 
			f[k] = iv[k + 1] * t % P * inv[k] % P ; 
		Fpow(A[i]), NTT(f, 1), NTT(Ans, 1) ;
		rep( k, 0, limit ) Ans[k] = Ans[k] * f[k] % P ; 
		NTT(Ans, 0) ; rep( k, m + 1, limit ) Ans[k] = 0 ;
		rep( k, 0, limit ) f[k] = 0 ; 
	}
	printf("%lld\n", Ans[m] % P ) ; 
	return 0 ;
}