#626415 (PyPy3) No.573 a^2[i] = a[i]

• 問題: No.573 a^2[i] = a[i]
• ユーザー: None
• 提出日時: 2021-03-06 18:34:06
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 5,374 bytes
• コンパイル時間: 409 ms
• コンパイル使用メモリ: 81,920 KB
• 実行使用メモリ: 84,992 KB
• 最終ジャッジ日時: 2024-10-08 19:09:31
• 合計ジャッジ時間: 3,828 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 12 WA * 35

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        PREP = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()
    def __call__(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
    def F(self, n):
        """ n! """
        return self.fac[n]
    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod
    def H(self, n, r):
        """ (箱区別:〇 ボール区別:× 空箱:〇) 重複組み合わせ nHm """
        if not 0 <= r <= n+r-1: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod
    def rising_factorial(self, n, r):
        """ 上昇階乗冪 n * (n+1) * ... * (n+r-1) """
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod
    def stirling_first(self, n, k):
        """ 第 1 種スターリング数  lru_cache を使うと O(nk)  # k 要素を n 個の巡回列に分割する場合の数 """
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod
    def stirling_second(self, n, k):
        """ 第 2 種スターリング数 O(k + log(n)) """
        if n == k: return 1                              # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod
    def grouping(self, n, k):
        """ (箱区別:× ボール区別:〇 空箱:×) 組み分け   mSn。第二種スターリング数と添え字を交換したもの """
        if n == k: return 1                             # n==k==0 のときのため
        return self.facinv[n] * sum((-1)**(n-m) * self.C(n, m) * pow(m, k, self.mod) for m in range(1, n+1)) % self.mod
    def sum_groupiing(self, n, k):
        """ (箱区別:× ボール区別:〇 空箱:〇) 重複順列    Σ_(l=1,...,n) mSl """
        return sum(self.grouping(n,m)for m in range(1, k+1)) % self.mod
    def balls_and_boxes(self, n, k):
        """ (箱区別:〇 ボール区別:〇 空箱:×) 組み分け    mSn * n!  O(k + log(n)) """
        return sum((-1)**(n-m) * self.C(n, m) * pow(m, k, self.mod) for m in range(1, n+1)) % self.mod
    def bernoulli(self, n):
        """ ベルヌーイ数。べき乗和を求める際に必要(Faulhaber の定理。 lru_cache を使うと O(n**2 * log(mod)) """
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod
    def faulhaber(self, k, n):
        """
        べき乗和 0^k + 1^k + ... + (n-1)^k
        bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        """
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range
            (k+1)) % self.mod
    def lah(self, n, k):
        """ n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1) """
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod
    def bell(self, n, k):
        """ n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod)) """
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod
    def montmort(self, n):
        """ 順列を置換した数列のうち、ai != i となるような数列の数 """
        return sum( (-1)**(k%2) * self.fac[n]*self.facinv[k] for k in range(2,n+1)) % self.mod
class Combination2:
    """ without mod """
    def __init__(self, n_max):
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i
            fac.append(f)
    def __call__(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] // self.fac[r] // self.fac[n-r]
    def F(self, n):
        """ n! """
        return self.fac[n]
    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] // self.fac[r] // self.fac[n-r]
    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] // self.fac[n-r]
    def H(self, n, r):
        """ (箱区別:〇 ボール区別:× 空箱:〇) 重複組み合わせ nHm """
        if not 0 <= r <= n+r-1: return 0
        return self.fac[n+r-1] // self.fac[r] // self.fac[n-1]
##############################################################################################
import sys
input = sys.stdin.readline
MOD=10**9+7
N=int(input())
C = Combination(N, MOD=MOD)
res=0
for k in range(N+1):
    res+=C(N,k)*pow(N-k,k,MOD)
print(res)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX