4.29 模拟赛

A 参见 JOI Open 2016 摩天大楼

B 小W玩游戏

这个操作了 $q$ 次后，等价于选 $q$ 行 $q$ 列分别 $+1$ ，使得最后有不超过 $k$ 个奇数。

把行列分开讨论。考虑把 $q$ 次操作写成一个序列，每个数大小在 $1\sim n$ 。我们假设钦定 $i$ 个数字被操作了奇数次的方案数量是 $g_i$ ，恰好有 $i$ 个数被操作了奇数次的方案数量是 $f_i$ ，那么由二项式反演我们有

$$g_i = \sum_{j \le i} f_i\binom i j \Rightarrow f_i = \sum_{j \ge i} (-1)^{j-i} \binom{j}{i} g_j$$

所以我们只需要求出 $g_i$ 我们就可以做个差卷积变回 $f_i$ 。假设我们已经知道了 $f_i$ 的值，不难发现答案就很好求了。考虑有 $i$ 行最后被操作了奇数次， $j$ 列被操作了偶数次，于是答案就是

$$\sum_{i=0}^n \sum_{j=0}^m [i(m-j)+j(n-i) \le k] f_{0,i}f_{1,j}$$

其中 $f_0$ 表示通过行推出来的 $f$ ，$f_1$ 表示通过列推出来的 $f$ 。这个东西很明显可以 $O(nm)$ 求，也可以稍微化下式子，发现 $f_1$ 需要的总是一段前缀或者后缀的形式，于是可以优化到 $O(n)$ ，具体来说，就是化成：

$$\begin{aligned} \sum_{i=0}^nf_0(i) \sum_{j=0}^m [j \le \frac{k-im}{n-2i}] f_1(j), n \ge 2i\\ \sum_{i=0}^nf_0(i) \sum_{j=0}^m [j \ge \frac{k-im}{n-2i}] f_1(j), n \le 2i \end{aligned}$$

现在的问题就是如何求 $g$ 。

偶数的 EGF 是

$$\frac{e^x-e^{-x}}{2}$$

于是，我们可以写出 $g$ 的式子：

$$\begin{aligned}g_i &= [x^q] q! \binom n i (\frac{e^x-e^{-x}}{2})^ie^{(n-i)x}\\&= [x^q] \frac{q!}{2^i} \binom n i (e^x-e^{-x}) e^{(n-i)x}\\&= [x^q] \frac{q!}{2^i} \binom n i \sum_{j=0}^i \binom i j e^{2xj-2ix+nx} (-1)^{i-j}\\&= \frac{q!}{2^i} \binom n i \sum_{j=0}^i \binom i j \frac{(2j-2i+n)^q}{q!} (-1)^{i-j}\\&= \frac{q!}{2^i} \binom n i \sum_{j=0}^i\binom i j \frac{(n-2j)^q}{q!} (-1)^j\end{aligned}$$

明显这是个卷积的形式。

珍珠就是这题的弱化版吧？

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
#define lg2( x ) ( 31 - __builtin_clz( x ) )
int n , m; ll q , k;

int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}

int Wn[2][MAXN] , rev[MAXN];
void getwn( int len ) {
    for( int mid = 1 ; mid < len ; mid <<= 1 ) {
        int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
        Wn[0][mid] = Wn[1][mid] = 1;
        for( int i = 1 ; i < mid ; ++ i )
            Wn[0][mid + i] = 1ll * Wn[0][mid + i - 1] * w0 % P,
            Wn[1][mid + i] = 1ll * Wn[1][mid + i - 1] * w1 % P;
    }
}
void getr( int len ) {
    int t = __builtin_ctz( len ) - 1;
    for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << t );
}
void NTT( int* A , int len , int typ ) {
    rep( i , 0 , len - 1 ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
    for( int mid = 1 ; mid < len ; mid <<= 1 )
        for( int i = 0 ; i < len ; i += ( mid << 1 ) )
            for( int k = 0 ; k < mid ; ++ k ) {
                int t1 = A[i + k] , t2 = 1ll * A[i + k + mid] * Wn[typ][mid + k] % P;
                A[i + k] = (t1 + t2) % P , A[i + k + mid] = (t1 + P - t2) % P;
            }
    if( typ == 1 ) for( int inv = Pow( len , P - 2 ) , i = 0 ; i < len ; ++ i ) A[i] = 1ll * A[i] * inv % P;
}

int J[MAXN] , iJ[MAXN];
int g[MAXN];
int a[MAXN] , b[MAXN] , iv2;
inline int pp( const int& x ) {
	return ( x & 1 ) ? P - 1 : 1;
}
inline void mul( int *A , int *B , int n , int m , int bc = 0 ) {
	int len = 1;
	while( len <= n + m ) len <<= 1;
	rep( i , n + 1 , len ) A[i] = 0;
	rep( j , m + 1 , len ) B[j] = 0;
	getr( len ) , getwn( len );
	NTT( A , len , 0 ) , NTT( B , len , 0 );
	rep( i , 0 , len - 1 ) A[i] = A[i] * 1ll * B[i] % P;
	NTT( A , len , 1 );
	if( !bc ) return;
	NTT( B , len , 1 );
} 
int C( int a , int b ) {
	return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}
void getg( int n ) {
	rep( i , 0 , n ) a[i] = pp( i ) * 1ll * iJ[i] % P * ( Pow( n - 2 * i , q ) % P + P ) % P , b[i] = iJ[i];
	mul( a , b , n , n );
	rep( i , 0 , n ) g[i] = a[i] * 1ll * J[i] % P * Pow( iv2 , i ) % P * C( n , i ) % P;
}

int f1[MAXN] , f2[MAXN] , s1[MAXN] , s2[MAXN];

void solve() {
	cin >> n >> m >> q >> k; q %= ( P - 1 );
	iv2 = ( P + 1 ) / 2;
	J[0] = 1;
	int mx = max( n , m );
	rep( i , 1 , mx ) J[i] = J[i - 1] * 1ll * i % P;
	iJ[mx] = Pow( J[mx] , P - 2 );
	per( i , mx - 1 , 0 ) iJ[i] = iJ[i + 1] * 1ll * ( i + 1 ) % P;
	
	getg( n );
	rep( i , 0 , n ) a[i] = pp( n - i ) * 1ll * iJ[n - i] % P , b[i] = J[i] * 1ll * g[i] % P;
	int len = 1;
	mul( a , b , n , n );
	rep( i , 0 , n ) f1[i] = a[i + n] * 1ll * iJ[i] % P;
	
	getg( m );
	rep( i , 0 , m ) a[i] = pp( m - i ) * 1ll * iJ[m - i] % P , b[i] = J[i] * 1ll * g[i] % P;
	len = 1;
	mul( a , b , m , m );
	rep( i , 0 , m ) f2[i] = a[i + m] * 1ll * iJ[i] % P;
	
	s1[0] = f2[0];
	rep( i , 1 , m ) s1[i] = ( s1[i - 1] + f2[i] ) % P;
	s2[m] = f2[m];
	per( i , m - 1 , 0 ) s2[i] = ( s2[i + 1] + f2[i] ) % P;
	
	int res = 0;
	rep( i , 0 , n / 2 ) { 
		ll t = ( k - i * 1ll * m );
		if( i + i != n )
			res += ( t < 0 ) ? 0 : f1[i] * 1ll * s1[min( ( t ) / ( n - 2 * i ) , 1ll * m )] % P , res %= P;
		else res += ( 0 <= t ) ? f1[i] * 1ll * s1[m] % P : 0, res %= P;
	}
	rep( i , n / 2 + 1 , n ) {
		ll t = ( k - i * 1ll * m );
//		ll pos = ( t + ( n - 2 * i - 1 ) ) / ( n - 2 * i );
		ll pos = ( -t + ( 2 * i - n - 1 ) ) / ( 2 * i - n );
		if( pos > m ) continue;
		pos = pos < 0 ? 0 : pos;
		res += f1[i] * 1ll * s2[ pos ] % P , res %= P;
	}
	cout << res << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}