牛客网笔试题逃离农场

你的名字 2021-12-04 07:21 270阅读 0赞

## 题意： ##

牛牛在农场饲养了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

## 分析：从0~n中选num个数和为n的倍数的情况，为背包问题，用dp\[i\]\[j\]\[k\]表示前i个数选j个，j个数的和对n取模为k的情况数，状态转移方程为dp\[i\]\[j\]\[k\]=dp\[i-1\]\[j\]\[k\]+dp\[i-1\]\[j-1\]\[(k-i+n)%n\] （选和不选当前数字i，拿上一次的凑对， +n防k比i小而漏算），压缩，相当于滚动数字（一维倒序01背包），dp\[j\]\[k\]=dp\[j\]\[k\]+dp\[j-1\]\[k-i+n)%n\]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int mod = 1e9+7;
    int n,k,dp[55][1005];
    int main() {
        cin>>n>>k;
        dp[0][0]=1;
        for(int i=0;i<n;i++)
            for(int j=k;j>=1;j--)
                for(int l=0;l<n;l++)
                    dp[j][l] = ( dp[j][l] + dp[j-1][(l-i+n)%n] )%mod;
        cout<<dp[k][0]<<endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，270人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客网刷题总结（一）-腾讯春招前端笔试题

.`$.ajax()`函数依赖服务器提供的信息来处理返回的数据。如果服务器报告说返回的数据是XML，那么返回的结果就可以用普通的XML方法或者jQuery的选择器来遍历。...

比眉伴天荒/ 2024年04月17日 05:59/ 0 赞/ 2 阅读

相关牛客刷题记录（常见笔试题）

目录一、Map的应用篇乒乓球筐简单的错误记录二、动态规划篇计算字符串的编辑距离年终奖最长不含重复字符的子字符串合唱团三、数组篇顺时针打

谁践踏了优雅/ 2023年09月23日 15:14/ 0 赞/ 79 阅读

相关牛客网 - 华为笔试题 - 循环链表

题目描述有一个数组a\[N\]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0

秒速五厘米/ 2022年10月24日 11:48/ 0 赞/ 141 阅读

相关逃离农场--动态规划

题目：牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和能被

偏执的太偏执、/ 2022年06月13日 09:07/ 0 赞/ 107 阅读

相关牛客网

package myTest; import java.util.; public class Stacktest { public stat

川长思鸟来/ 2022年05月28日 12:22/ 0 赞/ 213 阅读

相关牛客网笔试题错题总结

1、关于history对象的属性和方法的描述 length 返回浏览器历史列表中的URL数量 back() 加载 history 列表中的前一

亦凉/ 2022年05月13日 10:10/ 0 赞/ 193 阅读

相关牛客笔试题之机器学习

昨天做完了[牛客网][Link 1]上的机器学习试题，下面是对一些错题的分析，并简要总结了一些机器学习中应该注意的知识点，过段时间会对其中的一些方法进行更加详细的分析介绍。题中

痛定思痛。/ 2022年02月27日 18:12/ 0 赞/ 710 阅读

相关牛客笔试题之python

这几天做完了[牛客网][Link 1]上的Python试题，下面是对一些错题的分析，并总结了一些python中应该注意的知识点。字符串比较 ![1.png][]

以你之姓@/ 2022年02月27日 17:54/ 0 赞/ 370 阅读

相关牛客网笔试题随机的机器人（概率DP+滚动数组）

题意：有一条无限长的纸带,分割成一系列的格子,最开始所有格子初始是白色。现在在一个格子上放上一个萌萌的机器人(放上的这个格子也会被染红),机器人一旦走到某个格子上,就会

不念不忘少年蓝@/ 2021年12月04日 07:43/ 0 赞/ 163 阅读

相关牛客网笔试题逃离农场

题意：牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和

你的名字/ 2021年12月04日 07:21/ 0 赞/ 271 阅读