Submit Info #30387

Problem Lang User Status Time Memory
$\sum_{i=0}^{\infty} r^i i^d$ pypy3 convexineq AC 1387 ms 489.37 MiB

ケース詳細
Name Status Time Memory
0_00 AC 230 ms 183.09 MiB
0_01 AC 231 ms 183.09 MiB
0_02 AC 1346 ms 489.37 MiB
2_00 AC 230 ms 183.13 MiB
2_01 AC 232 ms 183.15 MiB
2_02 AC 243 ms 183.41 MiB
2_03 AC 286 ms 198.77 MiB
2_04 AC 1387 ms 489.34 MiB
2_05 AC 1336 ms 489.34 MiB
example_00 AC 231 ms 183.15 MiB

SIZE=10**7+5; MOD=998244353 #998244353 #ここを変更する fac = [0]*SIZE # fac[j] = j! mod MOD finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD fac[0] = fac[1] = 1 finv[0] = finv[1] = 1 for i in range(2,SIZE): fac[i] = fac[i-1]*i%MOD finv[-1] = pow(fac[-1],MOD-2,MOD) for i in range(SIZE-1,0,-1): finv[i-1] = finv[i]*i%MOD def choose(n,r): # nCk mod MOD の計算 if 0 <= r <= n: return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD else: return 0 """ a,b の convolution の、n-1 次までの和を r^{i} の重み付きで求める a,b は n 次以上 """ def sum_of_convolution(a,b,n,r): assert len(a) >= n and len(b) >= n if r != 1: R = 1 for i in range(n): a[i] = a[i]*R%MOD b[i] = b[i]*R%MOD R = R*r%MOD acc = res = 0 for i in range(n): acc += a[i] acc %= MOD res += acc*b[n-1-i]%MOD return res%MOD # coding: utf-8 # Your code here! import sys readline = sys.stdin.readline read = sys.stdin.read #n,q = map(int,readline().split()) r,d = map(int,input().split()) D = [0]*(d+1) #[pow(i,d,MOD) for i in range(d)] if d: D[1] = 1 else: D[0] = 1 #0^0 = 1 for p in range(2,d+1): if D[p]==0: #素数のとき pd = pow(p,d,MOD) for j in range(1,d//p+1): D[p*j] = (1 if D[j]==0 else D[j])*pd%MOD b = [choose(d+1,i)*(1-i%2*2) for i in range(d+1)] gr = sum_of_convolution(D,b,d+1,r) print(gr*pow(1-r,MOD-d-2,MOD)%MOD)