首页 > 试题广场 >

逃离农场

[编程题]逃离农场
  • 热度指数：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

输出

5
算法知识视频讲解
添加回答
Java
masami头像 masami
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        System.out.println(solve(n, k));
    }

    private static int solve(int n, int k) {
        int[][] dp = new int[k + 1][n];
        dp[0][0] = dp[1][0] = 1;
        int[] temp = new int[n];
        for (int i = 1; i < n; i++) {
            for (int j = Math.min(k, i + 1); j > 0; j--) {
                copyArray(dp[j], temp, n);
                for (int p = 0; p < n; p++) {
                    int r = p - i;
                    if (r < 0) r += n;
                    dp[j][p] = add(temp[p], dp[j - 1][r]);
                }
            }
        }
        return dp[k][0];
    }

    private static void copyArray(int[] from, int[] to, int length) {
        for (int i = 0; i < length; i++)
            to[i] = from[i];
    }

    private static int add(int a, int b) {
        int c = a + b;
        if (c >= MOD) c -= MOD;
        return c;
    }
}
发表于 2017-06-17 21:49:26 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 动态规划 测试开发工程师 大数据开发工程师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
1条回答 6945浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号