Đáp án+Giải thích các bước giải:

 giải thích đề : 

         +) bạn được cho 1 số nguyên dương n.

         +) xét tất cả tập con được gọi là hợp lệ nếu không có hai phần tử nào trong tập đó mà tổng của chúng là một số chính phương (ví dụ: 1, 4, 9, 16, 25...)

Ý tưởng: 

       +)dùng bitmask biểu diễn tập con đang chọn

        +)Nếu chọn phần tử i, ta cần đảm bảo không có phần tử nào đã chọn sao cho tổng là số chính phương.

        +)Sử dụng @lru_cache để memo hóa tránh tính lại.

đoạn code, mình tự viết bạn tham khảo:

import math

from functools import lru_cache

n, m = map(int, input().split())

a = set(i*i for i in range(1, int(2*n**0.5)+1))

b = [[False]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):

      for j in range(i+1, n+1):

            if i + j in a:

                b[i][j] = b[j][i] = True

@lru_cache(maxsize=None)

def dfs(i, mask):

        if i > n:

            return 1

        res = dfs(i+1, mask)

        for j in range(1, i):

             if (mask >> (j-1)) & 1 and b[i][j]:

                   return res

        res += dfs(i+1, mask | (1 << (i-1)))

        return res % m

print(dfs(1, 0))                     

                  -----không hiểu thì cứ hỏi mình nha-------

                              **chúc bạn học tốt**