QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297641#4903. 细菌luyiming123100 ✓1861ms25364kbC++147.5kb2024-01-04 21:21:382024-01-04 21:21:38

Judging History

你现在查看的是最新测评结果

  • [2024-01-04 21:21:38]
  • 评测
  • 测评结果:100
  • 用时:1861ms
  • 内存:25364kb
  • [2024-01-04 21:21:38]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long; 
const int N = 4.8e5 + 5; 
const i64 mod = 998244353, ivg = (mod + 1) / 3; 
void Add(i64 &x, i64 y) {x = (x + y) % mod; if(x < 0) x += mod; return; } 
int d, lim[3], pos[3], r[N], L; 
i64 Poly[3][N], fac[N], ifac[N]; 

struct node
{
	int l, r; i64 S; 
};
vector <node> Seg[2], FkSeg; 

i64 qpow(i64 x, i64 p = mod - 2ll)
{
    i64 ans = 1ll;
    while(p)
    {
        if(p & 1) ans = ans * x % mod; 
        x = x * x % mod, p >>= 1;
    }
    return ans; 
}

void NTT(i64 *a, bool type) {
	static ui64 f[N], w[N];
	for(int i = 0; i < L; i++) f[i] = a[r[i] = (r[i >> 1] >> 1) | (i & 1 ? L >> 1 : 0)];
	for(int d = 1; d < L; d <<= 1) {
		int wd = qpow(type ? 3 : ivg, (mod - 1) / (d + d));
		for(int j = w[0] = 1; j < d; j++) w[j] = 1ll * w[j - 1] * wd % mod;
		for(int i = 0; i < L; i += d << 1) {
			for(int j = 0; j < d; j++) {
				int y = w[j] * f[i | j | d] % mod;
				f[i | j | d] = f[i | j] + mod - y, f[i | j] += y;
			}
		}
		if(d == (1 << 16)) for(int p = 0; p < L; p++) f[p] %= mod;
	}
	i64 inv = qpow(L, mod - 2);
	for(int i = 0; i < L; i++) a[i] = f[i] % mod * (type ? 1 : inv) % mod;
}

void Init(int n = N - 5)
{
    fac[0] = ifac[0] = 1ll; 
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % mod; 
    ifac[n] = qpow(fac[n]); 
    for(int i = n - 1; i >= 1; i--) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % mod; 
    return; 
}

i64 C(int n, int m)
{
	if(n < m || n < 0 || m < 0) return 0; 
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod; 
}

i64 debtot = 0; 

void solve(int o, int d)
{
	// bool deb = (o == 0 && d == 1); 
	
	// bool deb = (o == 2); 
	// printf("solve : %d, %d\n", o, d); 
    int lim = ::lim[o], pos = ::pos[o]; 
    // Line : y = 0, y = lim + 1
    // Line : y = lim + 1 最后被触碰
    i64 Ans = 0; 
    // int lf = 0, rg = lim + 1; 
    int mx = min(d, (lim - pos + d) / 2), mn = (d + 1) / 2; 
	// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx); 
	// printf("mx = %d, mn = %d\n", mx, mn); 
    // Add(Ans, sumC[mx] - (mn > 0 ? sumC[mn - 1] : 0)); 
	// for(int i = mn; i <= mx; i++) Add(Ans, C(d, i)), ++debtot; 
	if(FkSeg.empty())
	{
		FkSeg.push_back({mn, mx, 0}); 
		for(int i = mn; i <= mx; i++) Add(FkSeg[0].S, C(d, i)); 
	}
	else
	{
		FkSeg[0].S = (FkSeg[0].S * 2ll % mod - C(d - 1, FkSeg[0].r) + C(d - 1, FkSeg[0].l - 1)) % mod; 
		for(int j = FkSeg[0].r + 1; j <= mx; j++) Add(FkSeg[0].S, C(d, j)), ++debtot; 
		FkSeg[0].r = mx; 
		for(int j = FkSeg[0].l; j < mn; j++) Add(FkSeg[0].S, -C(d, j)), ++debtot; 
		FkSeg[0].l = mn; 
	}
	Add(Ans, FkSeg[0].S); 
    //[lf, pos - 1]
	if(pos > 1)
	{		
		mx = (d - 1) / 2, mn = max(0, (2 - pos + d) / 2); 
		// printf("2 : mx = %d, mn = %d\n", mx, mn); 
		// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx); 
		// Add(Ans, sumC[mx] - (mn > 0 ? sumC[mn - 1] : 0)); 
		// for(int i = mn; i <= mx; i++) Add(Ans, C(d, i)), ++debtot; 
		if((int)FkSeg.size() < 2)
		{
			FkSeg.push_back({mn, mx, 0}); 
			for(int i = mn; i <= mx; i++) Add(FkSeg.back().S, C(d, i)); 
		}
		else
		{
			FkSeg[1].S = (FkSeg[1].S * 2ll % mod - C(d - 1, FkSeg[1].r) + C(d - 1, FkSeg[1].l - 1)) % mod; 
			for(int j = FkSeg[1].r + 1; j <= mx; j++) Add(FkSeg[1].S, C(d, j)), ++debtot; 
			FkSeg[1].r = mx; 
			for(int j = FkSeg[1].l; j < mn; j++) Add(FkSeg[1].S, -C(d, j)), ++debtot; 
			FkSeg[1].l = mn; 
		}
		Add(Ans, FkSeg[1].S); 
	}
	// if(deb) printf("Answer = %lld\n", Ans);  
    for(int i = 1; i * (lim + 1) + 1 <= pos + d; i++)
    {
		// fprintf(stderr, "step 1: o = %d, d = %d, i = %d\n", o, d, i); 
		// assert(1ll * i * (lim + 1) + 1 <= pos + d); 
        int lf = i * (lim + 1) + 1, rg = min((i + 1) * (lim + 1) - 1, pos + d); 
        int mx = (rg - pos + d) / 2, mn = (lf - pos + d + 1) / 2; 
		// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx); 
		if(i <= (int)Seg[0].size())
		{
			Seg[0][i - 1].S = (Seg[0][i - 1].S * 2ll % mod - C(d - 1, Seg[0][i - 1].r) + C(d - 1, Seg[0][i - 1].l - 1)) % mod; 
			for(int j = Seg[0][i - 1].r + 1; j <= mx; j++) Add(Seg[0][i - 1].S, C(d, j)), ++debtot; 
			Seg[0][i - 1].r = mx; 
			for(int j = Seg[0][i - 1].l; j < mn; j++) Add(Seg[0][i - 1].S, -C(d, j)), ++debtot; 
			Seg[0][i - 1].l = mn; 

		}
		else
		{
			Seg[0].push_back({mn, mx, 0}); 
			for(int j = mn; j <= mx; j++) Add(Seg[0].back().S, C(d, j)), ++debtot; 
		}
        Add(Ans, ((i & 1) ? -1 : 1) * Seg[0][i - 1].S); 
    }

    // Line : y = 0 最后被触碰 pos reverse
    pos = lim - pos + 1; 
    for(int i = 1; i * (lim + 1) + 1 <= pos + d; i++)
    {
		// fprintf(stderr "step 2: o = %d, d = %d, i = %d\n", o, d, i); 
        int lf = i * (lim + 1) + 1, rg = min((i + 1) * (lim + 1) - 1, pos + d); 
        int mx = (rg - pos + d) / 2, mn = (lf - pos + d + 1) / 2; 
		// printf("fuck : mx = %d, mn = %d\n", mx, mn); 
		// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx); 
		if(i <= (int)Seg[1].size())
		{
			Seg[1][i - 1].S = (Seg[1][i - 1].S * 2ll % mod - C(d - 1, Seg[1][i - 1].r) + C(d - 1, Seg[1][i - 1].l - 1)) % mod; 
			for(int j = Seg[1][i - 1].r + 1; j <= mx; j++) Add(Seg[1][i - 1].S, C(d, j)); 
			Seg[1][i - 1].r = mx; 
			for(int j = Seg[1][i - 1].l; j < mn; j++) Add(Seg[1][i - 1].S, -C(d, j)); 
			Seg[1][i - 1].l = mn; 

		}
		else
		{
			Seg[1].push_back({mn, mx, 0}); 
			for(int j = mn; j <= mx; j++) Add(Seg[1].back().S, C(d, j)); 
		}
        Add(Ans, ((i & 1) ? -1 : 1) * Seg[1][i - 1].S);
    }
    Poly[o][d] = Ans; 
	// printf("fkkkk!\n"); 
    return; 
}

void solve2(int o)
{
    int lim = ::lim[o], pos = ::pos[o]; 
    static i64 dp[2][N];
    int lf = 1 - pos + d, rg = lim - pos + d; 
    for(int i = 0; i <= (d << 1); i++) dp[0][i] = dp[1][i] = 0; 
    dp[0][d] = 1; 
    Poly[o][0] = 1; 
    for(int i = 1; i <= d; i++)
    {
        int op = (i & 1); 
        for(int j = lf; j <= rg; j++) dp[op][j] = 0; 
        for(int j = lf; j <= rg; j++)
        {
            if(j < rg) Add(dp[op][j + 1], dp[op ^ 1][j]); 
            if(j > lf) Add(dp[op][j - 1], dp[op ^ 1][j]); 
        }
        Poly[o][i] = 0; 
        for(int j = lf; j <= rg; j++) Add(Poly[o][i], dp[op][j]); 
    }
    return; 
}

int main(void)
{
    Init(); 
    scanf("%d", &d);
    for(int i = 0; i < 3; i++) scanf("%d", &lim[i]); 
    for(int i = 0; i < 3; i++) scanf("%d", &pos[i]); 

    //init sumC[i] (means C(d, 1) + ... + C(d, i))
	// printf("YES1\n"); 
    for(int o = 0; o < 3; o++) 
    {
        if(2ll * d < 1ll * lim[o] * lim[o]) 
        {
			Poly[o][0] = 1; 
			// for(int i = 0; i <= d; i++) sumC[i] = 0; 
			// sumC[0] = 1; 
			Seg[0].clear(), Seg[1].clear(); FkSeg.clear(); 
            for(int d0 = 1; d0 <= d; d0++) 
			{
				// for(int i = 0; i < d0; i++)
				// {
				// 	sumC[i] = sumC[i] * 2ll % mod - C(d0 - 1, i);
				// }
				// sumC[d0] = sumC[d0 - 1] + 1; 
				solve(o, d0); 
			}
			fprintf(stderr, "length : %d %d, debtot = %lld\n", (int)Seg[0].size(), (int)Seg[1].size(), debtot); 
        }
        else solve2(o); 
		// for(int i = 0; i <= d; i++) printf("Poly[%d][%d] = %lld\n", o, i, Poly[o][i]); 
		fprintf(stderr, "Yes : o = %d\n", o); 
    }
	for(int o = 0; o < 3; o++)
	{
		for(int i = 0; i <= d; i++) Poly[o][i] = Poly[o][i] * ifac[i] % mod; 
	}
	L = 1; 
	while(L <= (d << 1)) L <<= 1; 
	for(int o = 0; o < 3; o++) NTT(Poly[o], 1); 
	for(int i = 0; i < L; i++) Poly[0][i] = Poly[0][i] * Poly[1][i] % mod * Poly[2][i] % mod; 
	NTT(Poly[0], 0); 
	printf("%lld\n", Poly[0][d] * fac[d] % mod); 
    return 0;  
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 3ms
memory: 11172kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 3ms
memory: 11176kb

input:

50 49 44 48 49 15 25

output:

544847893

result:

ok 1 number(s): "544847893"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 3ms
memory: 12004kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 0ms
memory: 11756kb

input:

5000 4994 4997 4994 4399 1826 1332

output:

65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 15
Accepted

Test #5:

score: 15
Accepted
time: 266ms
memory: 25176kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 347ms
memory: 25132kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 36ms
memory: 25164kb

input:

120000 119999 1 1 19896 1 1

output:

68846585

result:

ok 1 number(s): "68846585"

Subtask #4:

score: 10
Accepted

Test #8:

score: 10
Accepted
time: 43ms
memory: 25224kb

input:

119000 119991 119991 1 23819 52139 1

output:

944500934

result:

ok 1 number(s): "944500934"

Subtask #5:

score: 15
Accepted

Dependency #4:

100%
Accepted

Test #9:

score: 15
Accepted
time: 86ms
memory: 25184kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 83ms
memory: 25160kb

input:

120000 13997 13997 1 9768 6131 1

output:

151873213

result:

ok 1 number(s): "151873213"

Subtask #6:

score: 35
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #11:

score: 35
Accepted
time: 506ms
memory: 25364kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 658ms
memory: 25168kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 1245ms
memory: 25192kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 1076ms
memory: 25180kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 912ms
memory: 25188kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 784ms
memory: 25176kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 662ms
memory: 25172kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 341ms
memory: 25188kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 170ms
memory: 25168kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 110ms
memory: 25180kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 58ms
memory: 25172kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 39ms
memory: 25128kb

input:

120000 119996 119994 1 58014 49559 1

output:

682979057

result:

ok 1 number(s): "682979057"

Subtask #7:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #23:

score: 10
Accepted
time: 747ms
memory: 25232kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 990ms
memory: 25164kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 1861ms
memory: 21420kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 1579ms
memory: 21432kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1348ms
memory: 21432kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 1205ms
memory: 21512kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 960ms
memory: 21416kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 511ms
memory: 21656kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 231ms
memory: 21664kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 138ms
memory: 21424kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 67ms
memory: 21412kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 47ms
memory: 21412kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"