コンテンツにスキップ

剰余

タグ「剰余」の記事 4 件

DOJ Beginner Contest 9 G - Pi Problem

正の整数 a,ba, b に対して、aa の十進表記を bb 回つなげた整数を rep(a,b)\mathrm{rep}(a, b) とします。たとえば rep(31,4)=31313131\mathrm{rep}(31, 4) = 31313131 です。

長さ NN の正整数列 AA が与えられるので、

∏1≤i<j≤Nrep(Ai,Aj)\prod_{1 \le i < j \le N} \mathrm{rep}(A_i, A_j)

を 998244353998244353 で割った余りを求める問題です。Ai≤109A_i \le 10^9 で、NN の総和は 2×1052 \times 10^5 以下です。

aa が kk 桁のとき、aa を bb 回つなげることは、aa に 1+10k+102k+⋯+10(b−1)k1 + 10^k + 10^{2k} + \dots + 10^{(b-1)k} を掛けることと同じです。等比数列の和を使うと

rep(a,b)=a⋅10kb−110k−1\mathrm{rep}(a, b) = a \cdot \frac{10^{kb} - 1}{10^k - 1}

です。以下、kk 桁の数を bb 回つなげたときに掛かる部分を fk(b)=10kb−110k−1f_k(b) = \dfrac{10^{kb} - 1}{10^k - 1} と書きます。

AiA_i の桁数を kik_i とすると、求める積は

∏i<jAi⋅fki(Aj)=(∏i<jAi)(∏i<jfki(Aj))\prod_{i < j} A_i \cdot f_{k_i}(A_j) = \left( \prod_{i < j} A_i \right) \left( \prod_{i < j} f_{k_i}(A_j) \right)

と分けられます。

前半では、AiA_i は自分より後ろの jj の個数だけ掛かるので、∏iAiN−i\prod_i A_i^{N - i} です。

後半は、jj ごとにまとめます。Ai≤109A_i \le 10^9 なので桁数 kk は 11 から 1010 までしかありません。i<ji < j で桁数が kk のものの個数を cj,kc_{j,k} とすると、後半は

∏j∏k=110fk(Aj)cj,k\prod_j \prod_{k=1}^{10} f_k(A_j)^{c_{j,k}}

です。cj,kc_{j,k} は桁数ごとの個数を数えながら jj を動かせば求まります。fk(Aj)f_k(A_j) は 11 つの jj につき 1010 通りしかないので、全体で O(10Nlog⁡A)O(10 N \log A) 回程度の計算で済みます。

fk(b)f_k(b) を 998244353998244353 で割った余り

Section titled “fk(b)f_k(b)fk​(b) を 998244353998244353998244353 で割った余り”

fk(b)f_k(b) は割り算を含みます。10k−110^k - 1 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。

M=998244353M = 998244353、d=10k−1d = 10^k - 1、X=10kb−1X = 10^{kb} - 1 とします。XX は dd で割り切れます。XX を dMdM で割った余りを rr とすると、X=q⋅dM+rX = q \cdot dM + r と書けて、rr も dd で割り切れます。両辺を dd で割ると

Xd=qM+rd\frac{X}{d} = qM + \frac{r}{d}

なので、Xd\dfrac{X}{d} を MM で割った余りは rd\dfrac{r}{d} を MM で割った余りと同じです。つまり、10kb10^{kb} を dMdM を法として計算し、11 を引いてから dd で割れば、fk(b)f_k(b) を MM で割った余りが求まります。

Python
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 1
d = [0] * 11
for i in range(N):
ans *= pow(A[i], N - i - 1, MOD)
ans %= MOD
d[len(str(A[i]))] += 1
for i in reversed(range(N)):
d[len(str(A[i]))] -= 1
for j in range(1, 11):
if d[j] == 0:
continue
b = 10**j - 1
x = pow(10, j * A[i], b * MOD)
x -= 1
x %= b * MOD
assert x % b == 0
x //= b
ans *= pow(x, d[j], MOD)
ans %= MOD
print(ans)

最初のループで前半の積を計算し、桁数ごとの個数 d を数えます。2 つ目のループでは後ろから見ていき、d から自分を引くことで、d[j] が「自分より前にある jj 桁の数の個数」になるようにしています。

DOJ Beginner Contest 9 E - 67

長さ NN の十進数 SS が与えられます。SS からいくつかの文字を消し、残った文字をそのままの順で並べた数を 66 の倍数か 77 の倍数にしたい問題です。残す文字は 11 個以上で、先頭が 00 になってもかまいません(00 も 66 と 77 の倍数です)。消す文字の個数の最小値を求め、できなければ −1-1 を出力します。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

42=6×742 = 6 \times 7 は 66 でも 77 でも割り切れるので、ある数が 66 の倍数か 77 の倍数かは、その数を 4242 で割った余り mm だけで決まります。mm が 66 の倍数か 77 の倍数であれば条件を満たします。

SS を先頭から 1 文字ずつ見ていき、

dp[m]=残した文字が表す数を 42 で割った余りが m になるときの、消した文字数の最小値\mathrm{dp}[m] = \text{残した文字が表す数を } 42 \text{ で割った余りが } m \text{ になるときの、消した文字数の最小値}

を更新します。最初は何も残していないので、dp[0]=0\mathrm{dp}[0] = 0、それ以外は ∞\infty です。

次の文字が数字 xx のとき、各 mm について 2 通りの遷移があります。

  • 消す:余りは mm のままで、消した文字数が 11 増えます。
  • 残す:余りは (10m+x) mod 42(10m + x) \bmod 42 になり、消した文字数は変わりません。

最後に、mm が 66 の倍数か 77 の倍数であるものについて dp[m]\mathrm{dp}[m] の最小値をとります。

ただし、全部消した場合も「余り 00、消した文字数 NN」として dp[0]\mathrm{dp}[0] に含まれています。残す文字は 11 個以上という条件があるので、dp[m]<N\mathrm{dp}[m] < N のものだけを答えの候補にします。候補がなければ −1-1 です。

計算量は O(42∑N)O(42 \sum N) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
dp = [float("inf")] * 42
dp[0] = 0
for c in S:
x = int(c)
ndp = [float("inf")] * 42
for i in range(42):
ndp[i] = dp[i] + 1
for i in range(42):
j = (i * 10 + x) % 42
ndp[j] = min(ndp[j], dp[i])
dp = ndp
ans = float("inf")
for i in range(42):
if i % 6 == 0 or i % 7 == 0:
if dp[i] < N:
ans = min(ans, dp[i])
if ans == float("inf"):
ans = -1
print(ans)

牛客小白月赛138 A - Sleeping Time

xx 時に寝始めて、tt 時間眠ります(0≤x≤230 \le x \le 23、1≤t≤501 \le t \le 50)。起きる時刻(0 時から 23 時のどれか)を求めてください。

時計は 24 時間で一周するので、答えは (x+t) mod 24(x + t) \bmod 24 です。

tt は最大 5050 で 24 時間を超えることがありますが、 mod 24\bmod 24 をとれば何周しても正しく求まります。たとえば x=10,t=50x = 10, t = 50 なら 60 mod 24=1260 \bmod 24 = 12 です。

Python
print(sum(map(int, input().split())) % 24)

SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K

長さ nn の数列 aa と整数 kk が与えられます。連続する部分列 al,…,ara_l, \ldots, a_r のうち、総和が kk で割り切れるものの個数を求める問題です(n≤105n \le 10^5、k≤109k \le 10^9、0≤ai≤1090 \le a_i \le 10^9)。

累積和を S0=0S_0 = 0、Si=a1+⋯+aiS_i = a_1 + \cdots + a_i とすると、区間 [l,r][l, r] の総和は Sr−Sl−1S_r - S_{l-1} です。これが kk で割り切れるのは

Sr≡Sl−1(modk)S_r \equiv S_{l-1} \pmod{k}

のときです。つまり、0≤i<j≤n0 \le i < j \le n で Si mod kS_i \bmod k と Sj mod kS_j \bmod k が等しい組 (i,j)(i, j) の個数が答えです。

j=0,1,…,nj = 0, 1, \ldots, n の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 jj について「Sj mod kS_j \bmod k と同じ余りの SiS_i が前に何個あったか」がすぐに分かります。全体で O(n)O(n) です。

Python
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
t = 0
C = Counter()
C[0] += 1
ans = 0
for a in A:
t += a
t %= K
ans += C[t]
C[t] += 1
print(ans)

t が累積和を kk で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で S0=0S_0 = 0 の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。

kk は最大 10910^9 なので、配列ではなく Counter(辞書)で数えています。