#759261 (PyPy3) No.196 典型DP (1)

提出ソース

結果

問題	No.196 典型DP (1)
ユーザー	vwxyz
提出日時	2022-05-08 16:18:22
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	9,476 bytes
コンパイル時間	312 ms
コンパイル使用メモリ	82,376 KB
実行使用メモリ	162,272 KB
最終ジャッジ日時	2024-07-08 04:38:54
合計ジャッジ時間	10,514 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	150 ms 94,464 KB
testcase_01	AC	154 ms 89,088 KB
testcase_02	AC	154 ms 89,088 KB
testcase_03	AC	151 ms 88,832 KB
testcase_04	AC	159 ms 88,960 KB
testcase_05	AC	154 ms 88,832 KB
testcase_06	AC	154 ms 88,960 KB
testcase_07	AC	151 ms 88,832 KB
testcase_08	AC	150 ms 88,832 KB
testcase_09	AC	155 ms 88,832 KB
testcase_10	AC	170 ms 89,728 KB
testcase_11	AC	189 ms 90,052 KB
testcase_12	AC	191 ms 89,984 KB
testcase_13	AC	198 ms 90,240 KB
testcase_14	AC	210 ms 90,368 KB
testcase_15	AC	272 ms 91,008 KB
testcase_16	AC	373 ms 92,224 KB
testcase_17	AC	436 ms 93,180 KB
testcase_18	AC	505 ms 95,596 KB
testcase_19	AC	543 ms 96,128 KB
testcase_20	AC	482 ms 94,208 KB
testcase_21	AC	503 ms 96,720 KB
testcase_22	AC	487 ms 94,428 KB
testcase_23	TLE	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if graph:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))
        else:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        finished=[False]*self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag=True
        if euler_tour:
            et=[]
        if linked_components:
            lc=[]
        if lowlink:
            order=[None]*self.V
            ll=[None]*self.V
            idx=0
        if parents or cycle_detection or lowlink or subtree_size:
            ps=[None]*self.V
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        if subtree_size:
            ss=[1]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[self.inf]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[self.inf]*self.V
            wd[s]=0
        stack=[(s,0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                x,d=stack.pop()
            else:
                x=stack.pop()
            if not seen[x]:
                seen[x]=True
                stack.append((x,d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x]=idx
                    ll[x]=idx
                    idx+=1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        stack.append((y,d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y]=x
                        if unweighted_dist or bipartite_graph:
                            uwd[y]=uwd[x]+1
                        if weighted_dist:
                            wd[y]=wd[x]+d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag=False
                            if cycle_detection:
                                cd=(y,x)
            elif not finished[x]:
                finished[x]=True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl=True
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if ps[x]==y and bl:
                            bl=False
                            continue
                        ll[x]=min(ll[x],order[y])
                    if x!=s:
                        ll[ps[x]]=min(ll[ps[x]],ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if y==ps[x]:
                            continue
                        ss[x]+=ss[y]
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                x,y=tpl[:2] if self.weighted else tpl
                if uwd[x]==self.inf or uwd[y]==self.inf:
                    continue
                if not uwd[x]%2^uwd[y]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if uwd[x]==self.inf:
                        continue
                    bg[uwd[x]%2].append(x)
        retu=()
        if bipartite_graph:
            retu+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            retu+=(cd,)
        if directed_acyclic:
            retu+=(dag,)
        if euler_tour:
            retu+=(et,)
        if linked_components:
            retu+=(lc,)
        if lowlink:
            retu=(ll,)
        if parents:
            retu+=(ps,)
        if postorder:
            retu+=(post,)
        if preorder:
            retu+=(pre,)
        if subtree_size:
            retu+=(ss,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            retu+=(tp_sort,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu

def FFT(polynomial0,polynomial1,digit=10**5):
    def DFT(polynomial,n,inverse=False):
        if inverse:
            primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
        else:
            primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
        if inverse:
            for bit in range(1,n+1):
                a=1<<bit-1
                for i in range(1<<n-bit):
                    for j in range(a):
                        s=i*2*a+j
                        t=s+a
                        polynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]
        else:
            for bit in range(n,0,-1):
                a=1<<bit-1
                for i in range(1<<n-bit):
                    for j in range(a):
                        s=i*2*a+j
                        t=s+a
                        polynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])

    def FFT_(polynomial0,polynomial1):
        N0=len(polynomial0)
        N1=len(polynomial1)
        N=N0+N1-1
        n=(N-1).bit_length()
        polynomial0=polynomial0+[0]*((1<<n)-N0)
        polynomial1=polynomial1+[0]*((1<<n)-N1)
        DFT(polynomial0,n)
        DFT(polynomial1,n)
        fft=[x*y for x,y in zip(polynomial0,polynomial1)]
        DFT(fft,n,inverse=True)
        fft=[round((fft[i]/(1<<n)).real) for i in range(N)]
        return fft

    N0=len(polynomial0)
    N1=len(polynomial1)
    N=N0+N1-1
    polynomial00,polynomial01=[None]*N0,[None]*N0
    polynomial10,polynomial11=[None]*N1,[None]*N1
    for i in range(N0):
        polynomial00[i],polynomial01[i]=divmod(polynomial0[i],digit)
    for i in range(N1):
        polynomial10[i],polynomial11[i]=divmod(polynomial1[i],digit)
    polynomial=[0]*(N)
    a=digit**2-digit
    for i,x in enumerate(FFT_(polynomial00,polynomial10)):
        polynomial[i]+=x*a
    a=digit-1
    for i,x in enumerate(FFT_(polynomial01,polynomial11)):
        polynomial[i]-=x*a
    for i,x in enumerate(FFT_([x1+x2 for x1,x2 in zip(polynomial00,polynomial01)],[x1+x2 for x1,x2 in zip(polynomial10,polynomial11)])):
        polynomial[i]+=x*digit
    return polynomial

N,K=map(int,readline().split())
edges=[]
for _ in range(N-1):
    a,b=map(int,readline().split())
    edges.append((a,b))
mod=10**9+7
G=Graph(N,edges=edges)
parents,tour=G.SIV_DFS(0,parents=True,postorder=True)
dp=[None]*N
for x in tour:
    dp[x]=[1]
    for y in G.graph[x]:
        if y==parents[x]:
            continue
        dp[x]=FFT(dp[x],dp[y])
        for i in range(len(dp[x])):
            dp[x][i]%=mod
    dp[x].append(1)
ans=dp[0][K]
print(ans)

yukicoder

結果

テストケース

ソースコード