소프티어

import sys

from collections import defaultdict

# N : 사람 수, M : 문자열 길이

N, M = map(int, sys.stdin.readline().split())

cpti = [int(sys.stdin.readline().rstrip(), 2) for _ in range(N)]

# 키가 없어도 기본값 0으로 할당

dct = defaultdict(int)

same_pair = 0

for i in range(N):

  same_pair += dct[cpti[i]] # 이전의 사람 중 똑같은 cpti를 가진 사람의 수 만큼 쌍을 더해줌

  # 비트 1개 반전 시키는 용도

  for j in range(M):

    # 모든 수와 0의 xor 연산은 자기 자신이 됨

    # 따라서 반전 시키고 싶은 비트에 1을 두면 그 자리의 수가 반전 됨

    new_cpti = cpti[i] ^ (1 << j) # 한 가지 영역이 다른 cpti

    same_pair += dct[new_cpti] # 새로운 cpti가 기존의 cpti에 있으면 더하기

    # 비트 2개 반전 시키는 용도

    for k in range(j+1 , M):

      new_cpti2 = new_cpti ^ (1 << k)

      same_pair += dct[new_cpti2]

  dct[cpti[i]] += 1

# 이전 코드의 시간 복잡도는 O(N^2*M)

# 이번 코드의 시간 복잡도는 O(N*M^2)

print(same_pair)

처음에 O(N^2*M)로 풀다가 N 범위가 크길래 O(N*M^2)로 다시 풀었는데도

계속 시간 초과 뜨길래 이상하다 싶어서 딥시크랑 챗지피티 한테 물어봐도

파이썬의 특성상 느린 실행 속도 때문에 여기서 더 최적화 시키기는 힘들다고 그러네요..

뭐 비틀어서 시간초를 0.01초라도 단축하는 방법이야 물론 찾아보면 있겠지만

이 문제에서 요구하는건 O(N^2*M)을 어떻게 O(N*M^2)로 푸냐는걸 물어보는 것 같은데

이렇게까지 몸을 비틀어서 풀어야 할까 싶어요 ㅠㅠ..