Вывод последних k цифр искомого количества последовательностей - C#

Узнай цену своей работы

Формулировка задачи:

Никак не могу понять как решить данную задачу. Если сказать точнее, я не понимаю как она должна работать. Мне не очень понятно как формируются выходные данные, и если бы кто нибудь сказал мне как например сформировалась тройка в первом примере, и почему во втором примере на выходе 1, я бы все понял. Спасибо!
Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей. Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних k цифр этого числа. Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу. Входные данные Первая строка входного файла содержит три целых числа — n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 10^8, 1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр. Выходные данные В выходной файл выведите последние k цифр искомого количества последовательностей (без ведущих нулей).
входные данные 3 11 2 111 выходные данные 3
входные данные 19 9 1 0123456789876543210 выходные данные 1
входные данные 1 8 3 9 выходные данные 0

Решение задачи: «Вывод последних k цифр искомого количества последовательностей»

textual
Листинг программы
using System;
using System.IO;
using System.Linq;
 
class Program
{
    static int Solve(int n, int c, int k, int[] seq)
    {
        k = (int)Math.Pow(10, k);
 
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = n - 1; i >= 0; i--)
        {
            if (seq[i] == 0) a[i] = 1;
            else
                for (int x = 0, j = i; j < n && x <= c; j++)
                {
                    x = x * 10 + seq[j];
                    if (x <= c) a[i]++;
                }
 
            if (i + a[i] >= n) b[i] = 1;
            for (int j = i + 1; j < i + a[i] + 1 && j < n; j++)
                b[i] = (b[i] + b[j]) % k;
        }
 
        return b[0];
    }
 
    static void Main()
    {
        var input = File.ReadAllLines("input.txt");
        var nck = input[0].Split().Take(3).Select(x => int.Parse(x)).ToArray();
        var seq = input[1].Select(x => x - '0').ToArray();
        var slv = Solve(nck[0], nck[1], nck[2], seq);
        File.WriteAllText("output.txt", slv.ToString());
    }
}

Оцени полезность:

11   голосов , оценка 4.182 из 5
Похожие ответы