#573852 (Crystal) No.1181 Product Sum for All Subsets

• 問題: No.1181 Product Sum for All Subsets
• ユーザー: yuruhiya
• 提出日時: 2020-10-31 12:32:37
• 言語: Crystal (1.14.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,455 bytes
• コンパイル時間: 11,499 ms
• コンパイル使用メモリ: 297,640 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-30 21:35:58
• 合計ジャッジ時間: 12,722 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

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
lib C
  fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64
end
class String
  def to_i64
    C.strtoll(self, nil, 10)
  end
end
struct ModInt
  @@MOD = 1_000_000_007i64
  def self.mod
    @@MOD
  end
  def self.zero
    ModInt.new(0)
  end
  def initialize(n)
    @n = n.to_i64 % @@MOD
  end
  getter n : Int64
  def + : self
    self
  end
  def - : self
    ModInt.new(n != 0 ? @@MOD - @n : 0)
  end
  def +(m)
    ModInt.new(@n + m.to_i64 % @@MOD)
  end
  def -(m)
    ModInt.new(@n - m.to_i64 % @@MOD)
  end
  def *(m)
    ModInt.new(@n * m.to_i64 % @@MOD)
  end
  def /(m)
    raise DivisionByZeroError.new if m == 0
    a, b, u, v = m.to_i64, @@MOD, 1i64, 0i64
    while b != 0
      t = a // b
      a -= t * b
      a, b = b, a
      u -= t * v
      u, v = v, u
    end
    ModInt.new(@n * u)
  end
  def //(m)
    self / m
  end
  def **(m : Int)
    t, res = self, ModInt.new(1)
    while m > 0
      res *= t if m.odd?
      t *= t
      m >>= 1
    end
    res
  end
  def ==(m)
    @n == m.to_i64
  end
  def !=(m)
    @n != m.to_i64
  end
  def succ
    self + 1
  end
  def pred
    self - 1
  end
  def to_i64 : Int64
    @n
  end
  delegate to_s, to: @n
  delegate inspect, to: @n
end
struct Int
  def to_mint : ModInt
    ModInt.new(self)
  end
end
class String
  def to_mint : ModInt
    ModInt.new(self)
  end
end
n, k = read_line.split.map(&.to_i64)
k = k.to_mint
puts (k*(k + 3)/2)**n - (k*(k + 1)/2)**n
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX