Задача
Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.
Входные данные
В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$
Выходные данные
Количество разных чисел.
Тесты
| Входные данные | Выходные данные |
| $5$ $3$ $13$ $85$ $45$ |
$4$ |
| $11$ $2$ $1$ $111$ |
$1$ |
| $11$ $3$ $11$ $8$ $11$ |
$0$ |
| $71$ $8$ $4018916609$ $7495223237$ $3405637482$ $3166003637$ $8998228133$ $1141886496$ $9124347310$ $7736090711$ |
$584$ |
Код программы
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static int k, d, quantity = 0; public static long[] was = new long[40320]; public static long[] nums = new long[9]; public static boolean Was(long h) { long c = 0; for (int i = 0; i < quantity; i++) { if (was[i] == h) c++; } if (c == 0) { was[quantity] = h; return true; } else return false; } public static void Swap(int a, int b) { long t = nums[a]; nums[a] = nums[b]; nums[b] = t; } public static void Generate(int n) { if (n == k) { long sum = 0; long p = 1; long h = 0; long hash = 1; for (int i = k - 1; i >= 0; i--) { long subs = nums[i]; sum += nums[i] % d * p; p *= Math.pow(10, (long)Math.log10(nums[i]) + 1); p = p%d; while (subs!= 0) { h += subs % 10 * hash; hash *= 101; subs /= 10; } } if (sum%d == 0 && Was(h) == true) { quantity++; } } else { for(int j = n; j < k;j++) { Swap(n,j); Generate(n+1); Swap(n,j); } } } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); d = in.nextInt(); k = in.nextInt(); for(int i = 0; i < k; i++) { nums[i] = in.nextLong(); } Generate(0); System.out.println(quantity); } } |
Решение задачи
Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.