Ящики і кульки#9557
Увійти

Ящики і кульки (Розбір)

У першу скриньку можна покласти будь-яку з куль. Колір кулі в другій скриньці повинен відрізнятися від кольору кулі в першій. Тому у другу скриньку можна покласти кулю будь-якого з n - 1 залишкових кольорів. В -у скриньку можна покласти кулю будь-якого кольору, відмінного від кольору кулі в (i - 1)-ій скриньці.

Таким чином, кількість різних варіантів розміщення куль по скриньках дорівнює

n \cdot (n - 1)^{n - 1}~mod~(10^9 + 7)

Реалізація алгоритму

Визначимо модуль, за яким будуть проводитися обчислення.

#define MOD 1000000007

Функція powmod обчислює значення x^n~mod~m.

long long powmod(long long x, long long n, long long m)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);
  return (x * powmod(x, n - 1, m)) % m;
}

Основна частина програми. Читаємо вхідне значення .

scanf("%lld", &n);

Визначаємо і виводимо відповідь.

res = (powmod(n - 1, n - 1, MOD) * n) % MOD;
printf("%d\n", res);

Java реалізація

import java.util.*;
 
public class Main
{
  public final static long MOD = 1000000007;
  
  static long PowMod(long x, long n, long m)
  {
    if (n == 0) return 1;
    if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
    return (x * PowMod(x, n - 1, m)) % m;
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long res = (PowMod(n - 1, n - 1, MOD) * n) % MOD;
    System.out.println(res);
    con.close();
  }
}
Java

Python реалізація — власна функція степеня

Функція myPow обчислює значення x^n~mod~m.

def myPow(x, n, m):
  if (n == 0): return 1
  if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)
  return (x * myPow(x, n - 1, m)) % m

Основна частина програми. Визначимо модуль mod = 10^9 + 7, за яким будемо виконувати обчислення.

mod = 10 ** 9 + 7

Читаємо вхідне значення .

n = int(input())

Визначаємо і виводимо відповідь.

print(n * myPow(n - 1, n - 1, mod) % mod)

Python реалізація

Визначимо модуль mod = 10^9 + 7, за яким будемо виконувати обчислення.

mod = 10 ** 9 + 7

Читаємо вхідне значення .

n = int(input())

Визначаємо і виводимо відповідь.

print(n * pow(n - 1, n - 1, mod) % mod)