1 条题解

  • 0
    @ 2026-1-16 23:01:25

    #include <bits/stdc++.h>
    #define N 530000
    #define lg2(x) (31 - __builtin_clz(x))
    
    typedef int vec[N], *pvec;
    typedef long long ll;
    const ll mod = 998244353, half_mod = 499122177, root = 31;
    
    ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}
    
    namespace Poly {
    	int l, n;
    	vec rev, x, y;
    
    	void in(int deg, pvec f) {for (int i = 0; i <= deg; ++i) scanf("%d", f + i);}
    
    	void out(int deg, pvec f, const char *_name){
    		printf("%s(x) =", _name);
    		for (int i = 0; i <= deg; ++i) printf(" %+d x^%d", (int)(f[i] - (mod & -(f[i] >= half_mod))), i);
    		putchar(10);
    	}
    
    	void series(int deg, pvec f) {for (int i = 0; i <= deg; ++i) printf("%d%c", f[i], i == deg ? 10 : 32);}
    
    	#define fy_out(deg, f) Poly::out(deg, f, #f)
    
    	void NTT_init(int len){
    		if (l == len) return; n = 1 << (l = len);
    		ll g = PowerMod(root, 1 << (23 - l));
    		*x = 1; *rev = 0;
    		for (int i = 1; i < n; ++i)
    			x[i] = x[i - 1] * g % mod, rev[i] = rev[i >> 1] >> 1 | (i & 1) << (l - 1);
    	}
    
    	void DNTT(int *d, int *t) {
    		int i, *j, *k, len = 1, delta = n, R;
    		for (i = 0; i < n; ++i) t[rev[i]] = d[i];
    		for (i = 0; i < l; ++i) {
    			delta >>= 1;
    			for (k = x, j = y; j < y + len; k += delta, ++j) *j = *k;
    			for (j = t; j < t + n; j += len << 1)
    				for (k = j; k < j + len; ++k) {
    					R = (ll)y[k - j] * k[len] % mod;
    					k[len] = (*k - R < 0 ? *k - R + mod : *k - R);
    					*k = (*k + R >= mod ? *k + R - mod : *k + R);
    				}
    			len <<= 1;
    		}
    	}
    
    	vec B1;
    
    	void Mul(int deg, pvec a, pvec b, pvec c) {
    		if (!deg) {*c = (ll)*a * *b % mod; return;}
    		NTT_init(lg2(deg) + 1);
    		int i; ll iv = PowerMod(n, mod - 2);
    		DNTT(a, c); DNTT(b, B1);
    		for (i = 0; i < n; ++i) B1[i] = (ll)B1[i] * c[i] % mod;
    		DNTT(B1, c); std::reverse(c + 1, c + n);
    		for (i = 0; i < n; ++i) c[i] = c[i] * iv % mod;
    	}
    }
    
    int n, d, x;
    vec f, g;
    vec fact, finv, E;
    
    void init(int n) {
    	int i;
    	for (*fact = i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
    	finv[n] = PowerMod(fact[n], mod - 2);
    	for (i = n; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
    	for (i = 0; i <= n; ++i) E[i] = (i & 1 ? mod - finv[i] : finv[i]);
    }
    
    int main() {
    	int i; ll A = 1, B = 1, ans = 0;
    	scanf("%d%d%d", &n, &d, &x);
    	Poly::in(d, f); init(d);
    	for (i = 0; i <= d; ++i) f[i] = (ll)f[i] * finv[i] % mod;
    	Poly::Mul(d * 2, f, E, g);
    	for (i = 0; i <= d; ++i) {
    		ans = (ans + A * B % mod * g[i]) % mod;
    		A = A * x % mod; B = B * (n - i) % mod;
    	}
    	printf("%lld\n", ans);
    	return 0;
    }
    
    
    • 1

    [清华集训 2016] 如何优雅地求和

    信息

    ID
    6399
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者