Qutular və toplar#9557

Qutular və toplar (Həll təhlili)

Birinci qutuya $n$ şarın hər hansı birini qoya bilərik. İkinci qutudakı şarın rəngi birinci qutudakı şarın rəngindən fərqli olmalıdır. Buna görə ikinci qutuya $n - 1$ n - 1 qalan rənglərdən istənilən rəngdə şar qoya bilərik. $i$ -ci qutuya $i - 1$ i-1-ci qutudakı şarın rəngindən fərqli hər hansı bir rəngdə şar qoya bilərik.

Beləliklə, şarların qutulara yerləşdirilməsinin fərqli variantlarının sayı bərabərdir:

n \cdot (n - 1)^{n - 1} m o d (1 0^{9} + 7)

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

Alqoritmin reallaşdırılması

Hesablamaların aparılacağı modulu təyin edək.

#define MOD 1000000007

powmod funksiyası $x^{n} m o d m$ x^n~mod~m dəyərini hesablayır.

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;
}

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyuruq.

scanf("%lld", &n);

Cavabı hesablayır və çıxışa yazırıq.

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

Java reallaşdırılması

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 reallaşdırılması — öz dərəcə funksiyası

myPow funksiyası $x^{n} m o d m$ x^n~mod~m dəyərini hesablayır.

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

Proqramın əsas hissəsi. Hesablamaları aparmaq üçün $m o d = 1 0^{9} + 7$ mod = 10^9 + 7 modulunu təyin edək.

mod = 10 ** 9 + 7

Giriş dəyəri $n$ -i oxuyuruq.

n = int(input())

Cavabı hesablayır və çıxışa yazırıq.

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

Python reallaşdırılması

Hesablamaları aparmaq üçün $m o d = 1 0^{9} + 7$ mod = 10^9 + 7 modulunu təyin edək.

mod = 10 ** 9 + 7

Giriş dəyəri $n$ -i oxuyuruq.

n = int(input())

Cavabı hesablayır və çıxışa yazırıq.

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