- Where there is a discrepancy between the answers for Si and Sj .
- If the discrepancies are even, the number of correct answers may match, if they are odd, there is no possibility.
- So for each digit we can take xor and see if it is 1:
- where xor is an operation that satisfies associative law, so the order can be changed:
- This still loops for i and j, so it would take 10^10 calculations.
- What to do with this?
- βTypical approach frequency table.
- A technique that can be used when the value type K is much less than N
- Pay to get the number of pieces of each type first
- Then the computation of the same value combination can be performed together, so .
- βTypical approach frequency table.
- This time K=2
- Pay and find the number x of those for which is 1 first
- This does not distinguish between large and small i and j, so the answer can be obtained by making Half of the queue. python
- What to do with this?
def main():
N, M = map(int, input().split())
s1 = 0
for i in range(N):
S = input().strip()
s = S.count(b"1")
if s % 2:
s1 += 1
print(s1 * (N - s1))
- If there exist A, B satisfying the condition
- , but can be set as [$ \min(B_j) = 0
- , since subtracting m from all Bs and adding m to all As does not change the result
- So , so ,
- Find C again with the obtained A and B, and check if it is constructed correctly. python
def solve(N, CS):
sums = [sum(row) for row in CS]
m = min(sums)
if any((x - m) % N for x in sums):
return ()
AS = [(x - m) // N for x in sums]
BS = [x - AS[0] for x in CS[0]]
if any(x < 0 for x in BS):
return ()
NCS = [tuple(AS[i] + BS[j] for j in range(N)) for i in range(N)]
if NCS != CS:
return ()
return (AS, BS)
- Think small first.
- When you draw this far, you realize, βOh, the number of prime factors.
- proof
- Items with K prime factors cannot be divisors of each other.
- So you can paint them the same color.
- Those with K prime factors always have at least one divisor with prime factors less than K.
- So it has to be a different color than those python
- Items with K prime factors cannot be divisors of each other.
def main():
N = int(input())
ret = []
for i in range(1, N + 1):
f = get_factors(i)
x = sum(f.values()) + 1
ret.append(x)
print(*ret)
- I looked at it for a while and thought, βI guess I need to find the connected components,β but I didnβt know where to go from there, so I first created a code to solve it with a full search. python
def blute(N,M,edges,edgelist):
ret = [0] * (N + 1)
for i in range(2 ** M):
deg = [0] * N
for j in range(M):
if i & (1 << j):
a, b = edgelist[j]
deg[a] += 1
deg[b] += 1
r = sum(x % 2 for x in deg)
ret[r] += 1
return ret
- What we learned from observation
- If not linked, find each and fold
- mounting
- Count the number of vertices and edges of connected components with UnionFind
- Create and set up an inverse/factorial table and calculate for each connected component
- Fold each of them in.
- Result TLE
- Post-Contest AC
- Cause of TLE: Using FFT library to compute convolution
- If you folded in a rustic loop, it was AC. py
- Cause of TLE: Using FFT library to compute convolution
def solve(N,M,edges,edgelist):
init_unionfind(N)
for x, y in edgelist:
unite(x, y)
comps = []
for x in range(N):
if find_root(x) == x:
comps.append((num_edges[x], num_vertex[x]))
MOD = 998_244_353
comb = CombinationTable(N + 10, MOD).comb
ret = None
for e, v in comps:
xs = [0] * (v + 1)
xs[0] = 1
for i in range(1, (v // 2) + 1):
xs[i * 2] = comb(v, 2 * i)
if e > v - 1:
m = pow(2, e - (v - 1), MOD)
xs = [x * m % MOD for x in xs]
if ret is None:
ret = xs
else:
ys = ret
ret = [0] * (len(xs) + len(ys) - 1)
for i in range(len(xs)):
for j in range(len(ys)):
ret[i + j] += xs[i] * ys[j]
ret[i + j] %= MOD
return ret
This page is auto-translated from /nishio/ARC115 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. Iβm very happy to spread my thought to non-Japanese readers.