Решение задачи "Машмох и ACM" с Codeforces

Без пояснения   Просмотров: 9

Бимоху, начальнику Машмоха, Машмох не нравился. Вот он его и уволил. Решил тогда Машмох новую работу не искать, а поступить в университет и поучаствовать в ACM. Машмох хочет попасть в команду Бамоха. Для этого ему дали (в качестве испытания) несколько задач по программированию и неделю на их решение. Машмох не шибко умудренный программист. В общем-то, он и не программист вовсе. Так что ничего он не решил, а попросил вас помочь ему с этими заданиями. Одно из них такое:

Последовательность из l целых чисел b 1, b 2, ..., b l (1 ≤ b 1 ≤ b 2 ≤ ... ≤ b l ≤ n) называется хорошей, если каждое число делит без остатка следующее число в последовательности. Более формально, для всех i (1 ≤ i ≤ l - 1).

Вам даны n и k, найдите количество хороших последовательностей длины k. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).

Код 

#include<bits/stdc++.h>
using namespace std;

const long long mod=1e9+7;
long long n,k,d[3000][3000],ans;

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		d[1][i]=1;
	for(int i=1;i<k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=j;k<=n;k+=j)
				d[i+1][k]=(d[i][j]+d[i+1][k])%mod;
		}
	}
	for(int i=1;i<=n;i++)
		ans+=d[k][i];
	cout<<ans%mod;
	return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться