首页 > 试题广场 >

逃离农场

[编程题]逃离农场

热度指数：1088 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和能被n整除。你现在需要帮牛牛计算有多少种不同的逃走的奶牛群。因为结果可能很大,输出结果对1,000,000,007取模。
例如n = 7 k = 4:
7只奶牛依次编号为0到6, 逃走了4只
编号和为7的有:{0, 1, 2, 4}
编号和为14的有:{0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6},{2, 3, 4, 5}
4只牛的编号和不会大于18,所以输出5.

输入描述:

输入包括一行,两个整数n和k(1 ≤ n ≤ 1000),(1 ≤ k ≤ 50),以空格分割。

输出描述:

输出一个整数表示题设所求的种数。

示例1

输入

7 4

输出

算法知识视频讲解

Python

锵域

# python多需要的时间太长了，智能过80

import sys
def function(n,k):
dp = [[0 for i in range(n+1)] for i in range(k+1)]
dp[0][0] = 1
for i in range(1,n+1):
for j in range(k,0,-1):
for t in range(0,n):
dp[j][t] = (dp[j][t] + dp[j - 1][((t + n) - i) % n]) % 1000000007
return dp[k][0]
nums = list(map(int,sys.stdin.readline().strip().split()))
print(function(nums[0],nums[1]))

编辑于 2019-07-18 17:33:50 回复(0)