#680743 (PyPy3) No.1614 Majority Painting on Tree

提出ソース

結果

問題	No.1614 Majority Painting on Tree
ユーザー	chineristAC
提出日時	2021-07-22 00:00:57
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	15,842 bytes
コンパイル時間	157 ms
コンパイル使用メモリ	82,848 KB
実行使用メモリ	273,188 KB
最終ジャッジ日時	2024-07-17 20:50:26
合計ジャッジ時間	48,671 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3,309 ms 262,516 KB
testcase_01	AC	1,278 ms 164,448 KB
testcase_02	AC	989 ms 150,392 KB
testcase_03	AC	1,545 ms 173,936 KB
testcase_04	AC	1,330 ms 184,280 KB
testcase_05	AC	1,318 ms 186,884 KB
testcase_06	AC	1,756 ms 201,280 KB
testcase_07	AC	1,284 ms 201,704 KB
testcase_08	AC	737 ms 183,984 KB
testcase_09	AC	1,038 ms 174,284 KB
testcase_10	AC	422 ms 150,124 KB
testcase_11	AC	1,216 ms 176,996 KB
testcase_12	AC	1,324 ms 177,392 KB
testcase_13	AC	974 ms 167,624 KB
testcase_14	AC	1,798 ms 182,472 KB
testcase_15	AC	1,694 ms 180,204 KB
testcase_16	AC	539 ms 155,372 KB
testcase_17	AC	944 ms 167,780 KB
testcase_18	AC	1,970 ms 205,932 KB
testcase_19	AC	930 ms 137,848 KB
testcase_20	AC	4,393 ms 267,744 KB
testcase_21	AC	4,925 ms 273,188 KB
testcase_22	TLE	-
testcase_23	AC	704 ms 124,140 KB
testcase_24	AC	4,591 ms 267,344 KB
testcase_25	AC	1,243 ms 148,964 KB
testcase_26	AC	2,750 ms 258,972 KB
testcase_27	AC	96 ms 82,664 KB
testcase_28	AC	99 ms 83,140 KB
testcase_29	AC	93 ms 82,584 KB
testcase_30	AC	104 ms 82,608 KB
testcase_31	AC	95 ms 82,536 KB
testcase_32	AC	96 ms 82,544 KB
testcase_33	AC	104 ms 82,784 KB
testcase_34	AC	96 ms 82,956 KB
testcase_35	AC	98 ms 82,968 KB
testcase_36	AC	60 ms 72,796 KB
testcase_37	AC	60 ms 73,408 KB
testcase_38	AC	60 ms 73,108 KB
testcase_39	AC	73 ms 78,456 KB
testcase_40	AC	61 ms 72,968 KB
testcase_41	AC	60 ms 71,944 KB
testcase_42	AC	60 ms 71,748 KB
testcase_43	AC	60 ms 71,528 KB
testcase_44	AC	59 ms 73,220 KB
testcase_45	AC	62 ms 73,508 KB
testcase_46	AC	62 ms 72,196 KB
testcase_47	AC	59 ms 72,892 KB
testcase_48	AC	61 ms 72,736 KB

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

ソースコード

raw source code

def divisors(M):
    d=[]
    i=1
    while M>=i**2:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    return d

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def eratosthenes(n):
    res=[0 for i in range(n+1)]
    prime=set([])
    for i in range(2,n+1):
        if not res[i]:
            prime.add(i)
            for j in range(1,n//i+1):
                res[i*j]=1
    return prime

def factorization(n):
    res=[]
    for p in prime:
        if n%p==0:
            while n%p==0:
                n//=p
            res.append(p)
    if n!=1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2,n+1):
        if x ** 2 > n:
            break
        if n%x==0:
            res = res//x * (x-1)
            while n%x==0:
                n //= x
    if n!=1:
        res = res//n * (n-1)
    return res

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p]+1):
                newres.append(d*p**j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):#排他的論理和の階乗
    if num==0:
        return 0
    elif num==1:
        return 1
    elif num==2:
        return 3
    elif num==3:
        return 0
    else:
        x=baseorder(num)
        return (2**x)*((num-2**x+1)%2)+function(num-2**x)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

def merge_sort(A,B):
    pos_A,pos_B = 0,0
    n,m = len(A),len(B)
    res = []
    while pos_A < n and pos_B < m:
        a,b = A[pos_A],B[pos_B]
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]]!=stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        self.group -= 1

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class WeightedUnionFind():
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.val = [0 for i in range(N)]
        self.flag = True
        self.edge = [[] for i in range(N)]

    def dfs(self,v,pv):
        stack = [(v,pv)]
        new_parent = self.parent[pv]
        while stack:
            v,pv = stack.pop()
            self.parent[v] = new_parent
            for nv,w in self.edge[v]:
                if nv!=pv:
                    self.val[nv] = self.val[v] + w
                    stack.append((nv,v))

    def unite(self,x,y,w):
        if not self.flag:
            return
        if self.parent[x]==self.parent[y]:
            self.flag = (self.val[x] - self.val[y] == w)
            return

        if self.size[self.parent[x]]>self.size[self.parent[y]]:
            self.edge[x].append((y,-w))
            self.edge[y].append((x,w))
            self.size[x] += self.size[y]
            self.val[y] = self.val[x] - w
            self.dfs(y,x)
        else:
            self.edge[x].append((y,-w))
            self.edge[y].append((x,w))
            self.size[y] += self.size[x]
            self.val[x] = self.val[y] + w
            self.dfs(x,y)

class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add_edge(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

class BIT():
    def __init__(self,n,mod=0):
        self.BIT = [0]*(n+1)
        self.num = n
        self.mod = mod

    def query(self,idx):
        res_sum = 0
        mod = self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            if mod:
                res_sum %= mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod = self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            if mod:
                self.BIT[idx] %= mod
            idx += idx&(-idx)
        return

class dancinglink():
    def __init__(self,n,debug=False):
        self.n = n
        self.debug = debug
        self._left = [i-1 for i in range(n)]
        self._right = [i+1 for i in range(n)]
        self.exist = [True for i in range(n)]

    def pop(self,k):
        if self.debug:
            assert self.exist[k]
        L = self._left[k]
        R = self._right[k]
        if L!=-1:
            if R!=self.n:
                self._right[L],self._left[R] = R,L
            else:
                self._right[L] = self.n
        elif R!=self.n:
            self._left[R] = -1
        self.exist[k] = False

    def left(self,idx,k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._left[res]
            if res==-1:
                break
            k -= 1
        return res

    def right(self,idx,k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._right[res]
            if res==self.n:
                break
            k -= 1
        return res

class SparseTable():
    def __init__(self,A,merge_func,ide_ele):
        N=len(A)
        n=N.bit_length()
        self.table=[[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func=merge_func

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=self.merge_func(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return self.merge_func(self.table[s][m],self.table[t-2**m+1][m])

class BinaryTrie:
    class node:
        def __init__(self,val):
            self.left = None
            self.right = None
            self.max = val

    def __init__(self):
        self.root = self.node(-10**15)

    def append(self,key,val):
        pos = self.root
        for i in range(29,-1,-1):
            pos.max = max(pos.max,val)
            if key>>i & 1:
                if pos.right is None:
                    pos.right = self.node(val)
                    pos = pos.right
                else:
                    pos = pos.right
            else:
                if pos.left is None:
                    pos.left = self.node(val)
                    pos = pos.left
                else:
                    pos = pos.left
        pos.max = max(pos.max,val)

    def search(self,M,xor):
        res = -10**15
        pos = self.root
        for i in range(29,-1,-1):
            if pos is None:
                break

            if M>>i & 1:
                if xor>>i & 1:
                    if pos.right:
                        res = max(res,pos.right.max)
                    pos = pos.left
                else:
                    if pos.left:
                        res = max(res,pos.left.max)
                    pos = pos.right
            else:
                if xor>>i & 1:
                    pos = pos.right
                else:
                    pos = pos.left

        if pos:
            res = max(res,pos.max)
        return res

def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n
    for v in range(n):
        if used[v]:
            continue
        y = dfs(v)
        if y!=0:
            return False
    return x

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

class slope_trick():
    def __init__(self):
        self.L = [10**17]
        self.R = [10**17]
        self.min_f = 0

        self.x_move = 0

    def move(self,a):
        self.x_move += a

    def add_right(self,a):
        a -= self.x_move
        l0 = -self.L[0]
        if l0 <= a:
            heappush(self.R,a)
        else:
            heappush(self.L,-a)
            heappush(self.R,-heappop(self.L))

        self.min_f  = self.min_f + max(0,l0-a)

    def add_left(self,a):
        a -= self.x_move
        r0 = self.R[0]

        if a <= r0:
            heappush(self.L,-a)
        else:
            heappush(self.R,a)
            heappush(self.L,-heappop(self.R))

        self.min_f = self.min_f + max(0,a-r0)

    def add_abs(self,a):
        self.add_left(a)
        self.add_right(a)

    def change_min_left(self):
        self.R = [10**17]

    def change_min_right(self):
        self.L = [10**17]


import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return (g1[n] * g2[r] % mod) * g2[n-r] % mod

mod = 998244353
N = 2*10**5
g1 = [1]*(N+1)
g2 = [1]*(N+1)
inverse = [1]*(N+1)

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

N,C = mi()
edge = [[] for v in range(N)]
for _ in range(N-1):
    a,b = mi()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

parent = [-1 for v in range(N)]
topo = []
deq = deque([0])
while deq:
    v = deq.popleft()
    topo.append(v)
    for nv in edge[v]:
        if parent[v]==nv:
            continue
        parent[nv] = v
        deq.append(nv)

def solve(k):
    dp = [0 for v in range(N)]
    pow_k = [1 for i in range(N+1)]
    for i in range(1,N+1):
        pow_k[i] = (k-1) * pow_k[i-1] % mod

    for v in topo[::-1]:
        m = len(edge[v])//2 + 1
        n = len(edge[v])
        if v!=0 and n==1:
            dp[v] = 1
            continue

        #all
        tmp = 1
        for nv in edge[v]:
            if nv==parent[v]:
                continue
            tmp *= dp[nv]
            tmp %= mod

        #not 過半数
        ALL = tmp * pow(k,n-1,mod) % mod
        #過半数: cならm-1以上 そうでないならm以上
        minus = 0
        for i in range(n):
            if m <= i:
                minus += cmb(n-1,i,mod) * pow_k[n-1-i] % mod
                minus %= mod

        dp[v] = tmp + ALL - ((minus * tmp % mod) * k % mod) - ((cmb(n-1,m-1,mod) * pow_k[n-1-(m-1)] % mod) * tmp % mod)
        dp[v] %= mod

    v = 0
    m = len(edge[v])//2 + 1
    n = len(edge[v])

    #all
    tmp = 1
    for nv in edge[v]:
        tmp *= dp[nv]
        tmp %= mod

    #not 過半数
    ALL = tmp * pow(k,n,mod)
    minus = 0
    for i in range(n+1):
        if m <= i:
            minus += cmb(n,i,mod) * pow_k[n-i] % mod
            minus %= mod

    dp[v] = k * tmp + ALL - minus * tmp * k
    dp[v] %= mod

    return dp[v]

res = 0
for k in range(1,C+1):
    if (C-k)&1:
        res -= solve(k) * cmb(C,k,mod)
    else:
        res += solve(k) * cmb(C,k,mod)

    #print(solve(k))
    res %= mod

print(res)

yukicoder

結果

テストケース

ソースコード