글 읽기 - ㄹㄽ

lkyxbar 1년 전 0

tnc값은 문제 없습니다 근데 cnt값은 문제가 있는데 fft과정이 잘못된것이라 생각합니다 어디서 잘못 된걸까요?

import sys
from math import sin, cos, pi
def fft(P, W):
    n=len(P)
    if not ~-n:
        return
    even, odd=P[0::2], P[1::2]
    fft(even, W*W)
    fft(odd, W*W)
    wp=complex(1, 0)
    for i in range(n//2):
        P[i]=even[i]+wp*odd[i]
        P[i+n//2]=even[i]-wp*odd[i]
        wp*=W

def mul(vec1):
    n=1
    while n<len(vec1)+1:
        n+=n
    n+=n
    vec1+=[0]*(n-len(vec1))
    vec3=[0 for _ in range(n)]
    w=complex(cos(2*pi/n), sin(2*pi/n))
    fft(vec1, w)
    for i in range(n):
        vec3[i]=vec1[i]*vec1[i]
    fft(vec3, w.conjugate())
    for i in range(n):
        vec3[i]=round((vec3[i]/n).real)
    return vec3
N=int(sys.stdin.readline())
f=[0]*N
cnt, tnc=0, 0
for i in range(1, N):
    f[i*i%N]+=1
for i in range(1, N):
    tnc+=f[2*i*i%N]
ans=mul(f)
for i in range(1, N):
    cnt+=ans[i] if f[i] else 0
print(cnt, tnc)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

ㄹㄽ

lkyxbar 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말