結果
問題 | No.1181 Product Sum for All Subsets |
ユーザー |
|
提出日時 | 2020-11-29 01:57:41 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 2,692 bytes |
コンパイル時間 | 15,324 ms |
コンパイル使用メモリ | 446,232 KB |
実行使用メモリ | 54,500 KB |
最終ジャッジ日時 | 2024-09-13 01:48:03 |
合計ジャッジ時間 | 24,714 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.InputStreamimport java.io.PrintWriterimport java.util.*// ModInt// regionclass ModInt(x: Long) {companion object {const val MOD = 1000000007L//const val MOD = 998244353L}val x = (x % MOD + MOD) % MODoperator fun plus(other: ModInt): ModInt {return ModInt(x + other.x)}operator fun minus(other: ModInt): ModInt {return ModInt(x - other.x)}operator fun times(other: ModInt): ModInt {return ModInt(x * other.x)}operator fun div(other: ModInt): ModInt {return this * other.inv()}fun pow(exp: Long): ModInt {if (exp == 0L) return ModInt(1L)var a = pow(exp shr 1)a *= aif (exp and 1L == 0L) return areturn this * a}fun inv(): ModInt {return this.pow(MOD - 2)}override fun equals(other: Any?): Boolean {if (this === other) return trueif (javaClass != other?.javaClass) return falseother as ModIntif (x != other.x) return falsereturn true}override fun hashCode(): Int {return x.hashCode()}override fun toString(): String {return "$x"}}val fac = mutableListOf<ModInt>()val invfac = mutableListOf<ModInt>()fun fact(n: Long, b: Boolean): ModInt {if (fac.count() == 0) {fac.add(ModInt(1))invfac.add(ModInt(1))}while (fac.count() <= n) {fac.add(fac.last() * ModInt(fac.count().toLong()))invfac.add(fac.last().inv())}return if (b) {fac[n.toInt()]} else {invfac[n.toInt()]}}fun comb(n: Long, k: Long): ModInt {return fact(n, true) * fact(k, false) * fact(n - k, false)}fun comb2(n: Long, k: Long): ModInt {var ans = ModInt(1)for (i in 0 until k) {ans = ans * ModInt(n - i) / ModInt(k - i)}return ans}// endregionfun PrintWriter.solve() = with(FastScanner(System.`in`)) {val n = nextLong()val k = nextLong()val a = ModInt(k) * ModInt(k + 3) / ModInt(2)val b = ModInt(k) * ModInt(k + 1) / ModInt(2)println(a.pow(n) - b.pow(n))}fun main() {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}class FastScanner(s: InputStream) {private var st = StringTokenizer("")private val br = s.bufferedReader()fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()fun nextDouble() = next().toDouble()}