首页 > 试题广场 >

小猿的击鼓传花

[编程题]小猿的击鼓传花

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

K(K>=3)个猿辅导的老师们在玩一个击鼓传花的小游戏。每击一次鼓，拿着花的老师要将花交给别人，不能留在自己手中。游戏开始前花在小猿手中，求击了N次鼓后，这朵花又回到小猿手中的方案数，请输出这个数模1000000007后的结果。

输入描述:

输入两个数N，K。

20%的数据：(3<=K<=10, 1<= N<=10)

70%的数据：(3<=K<=1000, 1<= N<=1000)

100%的数据：(3<=K<=10^9, 1<= N<=10^9)

输出描述:

输出方案数模1000000007后的结果

示例1

输入

3 3

输出

算法知识视频讲解

牛客279810500号

只能通过70%,有没有大佬帮忙看看哪里出错了

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	long long n, k;
	cin >> n >> k;
	if (k < 3)return 0;
	vector<vector<long long>>dp(n + 1, vector<long long>(k + 1));
	dp[0][0] = 1;
	dp[0][1] = 0;
	for (long long i = 1; i <= n; i++)
	{
		dp[i][0] = dp[i - 1][1] % 1000000007;
		dp[i][1] = (dp[i - 1][0] * (k - 1)) % 1000000007 + (dp[i - 1][1] * (k - 2)) % 1000000007;
	}
	cout << dp[n][0] << endl;
	system("pause");
	return 0;
}

发表于 2020-06-02 21:56:42 回复(7)

C/C++

frostmonarch

需要用矩阵快速幂加上DP.

大家可以参考上面的java大佬的解答。

首先，我们可以设计状态为an,bn;

an代表我们传到第n个人了，且第n个人是小猿，那么此时有多少个方案。

bn代表我们传到第n个人了，且第n个人不是小猿，那么此时有多少个方案。

那么

a_n=b_n-1

因为此时第n个时刻已经固定好是小猿了，那么第n-1个时刻只能是其它人咯。

b_n=(k-1)*a_n-1+(k-2)*b_n-1

这个就是说，我们第n个时刻，之和前面的一个时刻有关，当n-1个时刻是小猿的话，那么第n个位置有(k-1)种选择方法。当n-1个时刻不是小猿，那么我们第n个位置只有k-2种选择方法，因为我们不能选择小猿+(n-1)个时刻时候的那个人，其实就是简单的组合数学的思想。

最后化简表达式，我们得到：

a_n+1=(k-1)*a_n-1+(k-2)*a_n

为了加快计算，我们需要用到矩阵乘法（别问为什么想到，这问ACM大佬）

我们用矩阵表达上面的表达式：

$Y=B^{n-2}*X \\ B=\begin{bmatrix} k-2 & k-1 \\ 1 & 0 \end{bmatrix}\quad \\ X=\begin{bmatrix} k-1 \\ 0 \end{bmatrix}\quad$

结果是Y[0][0].

其中怎么计算矩阵的幂次，需要用到矩阵快速幂，要回矩阵快速幂先看看快速幂怎么实现的，然后再来学矩阵快速幂，这里不讨论矩阵快速幂怎么算了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MODN=1000000007;
vector<vector<int>>  mul(vector<vector<int>> &a,vector<vector<int>> &b){
    vector<vector<int>> ret(2,vector<int>(2,0));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                ret[i][j]+=a[i][k]*b[k][j],ret[i][j]%=MODN;
    return ret;
}
vector<vector<int>> quick_pow(vector<vector<int>> & mat,int n){
    vector<vector<int>> ret = {{1,0},{0,1}};
    while(n){
        if(n&1)ret=mul(ret,mat);
        mat=mul(mat,mat);
        n>>=1;
    }
    return ret;
}
int32_t main(){
    int n,k;cin>>n>>k;
    if(n==1)cout<<0<<endl;
    else if(n==2)cout<<k-1<<endl;
    else{
    vector<vector<int>> mat={{k-2,k-1},{1,0}};
    mat=quick_pow(mat,n-2);
    int ret=0;
    vector<int> mv={k-1,0};
    for(int i=0;i<2;i++)ret+=mat[0][i]*mv[i],ret%=MODN;
    cout<<ret<<endl;
    }
    return 0;
}

编辑于 2020-07-31 10:19:18 回复(4)

1+½+¼+⅛+...

import java.util.*;
 
public class Main{
 
    public static void main(String[] args){
        Scanner input;
        int N, K;
 
        input = new Scanner(System.in);
        while(input.hasNext()){
            N = input.nextInt();
            K = input.nextInt();
            System.out.println(new Main().Solution(N, K));
        }
    }
 
    private long Solution(int N, int K){
        int M;
        long[][] A, An;
 
        M = 1000000007;
        if(N == 1)
            return 0;
        if(N == 2)
            return K - 1;
        A = new long[][]{{K - 2, 1}, {K - 1, 0}};
        An = pow(A, N - 2);
        return An[0][0] * (K - 1) % M;
    }
 
    private long[][] pow(long[][] A, int n){
        Stack<Integer> stack;
        long[][] ans;
 
        stack = new Stack<>();
        ans = new long[][]{{1, 0}, {0, 1}};
        while(n > 0){
            stack.push(n % 2);
            n /= 2;
        }
        while(!stack.isEmpty()){
            multi(ans, ans);
            if(stack.pop() == 1)
                multi(ans, A);
        }
        return ans;
    }
 
    private void multi(long[][] A, long[][] B){
        long a00, a01, a10, a11;
        int M;
 
        M = 1000000007;
        a00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % M;
        a01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % M;
        a10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % M;
        a11 = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % M;
        A[0][0] = a00;
        A[0][1] = a01;
        A[1][0] = a10;
        A[1][1] = a11;
    }
}

发表于 2019-12-15 11:09:24 回复(1)

YTMartian

坑点在取模，乘法套加法的别乱取模，如 $(a+b \% p) \% p != (a+b) \% p$

通过画一棵树分析，如1的子节点可以有2,3,4...，找出规律 $f(n)=(k-1)^{n-1}-f(n-1)=(k-1)^{n-1}-(k-1)^{n-2}+f(n-2)=...$ ，除了 $(k-1)^{n-1}$ 之外，另一部分为首项是 $k-1$ ，公差是 $-(k-1)$ 的等比数列，根据 $n$ 的奇偶性来决定加上还是减去这一部分，于是式子可以化简为 $f(n)=\frac{(k-1)[(k-1)^{(n-1)}+(-1)^n]}{k} \% p$ ，又 $\frac{a}{b} \% p = a \times b^{(p-2)} \% p$ , 于是 $f(n)=(k-1)[(k-1)^{(n-1)}+(-1)^n] \times k^{(p-2)} \% p$

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

long long p = 1000000007;

long long quick_pow(long long a, long long b) {
    long long ans = 1;
    while(b) {
        if(b & 1)ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main() {

    long long n, k;
    cin >> n >> k;
    if(n == 1) {
        cout << 0 << endl;
        return 0;
    } else if(n == 2) {
        cout << k - 1 << endl;
        return 0;
    }
    long long ans = 0;
    long long odd = n % 2 == 1 ? -1 : 1; //(-1)^n
    ans = ((k - 1) * (quick_pow(k - 1, n - 1) + odd)) % p;//(k-1)*[(k-1)^(n-1)+(-1)^n]
    ans = ans * quick_pow(k, p - 2);
    ans %= p;
    cout << ans << endl;

    return 0;
}

发表于 2021-03-26 22:03:56 回复(0)

madlife111

求大佬看看这哪里错了能通过50%的case

import java.util.Scanner;
import java.lang.Math;

public class Main{
  public   static void main(String[] args)
    {
        int s=1000000007;
        Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        int n=sc.nextInt();
        long[] f=new long[n+3];
        f[2]=k-1;f[1]=0;
        long sum=(k-1);
        for(int i=3;i<=n;i++)
        {
            sum=sum*(k-1); //k=951   n=223
            f[i]=(sum-f[i-1])%s;
            sum=sum%s;
        }
      
        System.out.print(f[n]>=0?f[n]:f[n]+s);
            
    }
}

发表于 2021-03-26 21:07:28 回复(0)

zjtd_zd

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static final int mod=1000000007;
    public static void main(String[] args) {
        Scanner sin=new Scanner(System.in);
        while(sin.hasNext()){
            int n=sin.nextInt();
            int k=sin.nextInt();
            System.out.println(calcu(n,k));
        }
    }
    public static long calcu(int n,int k){
        //求dp[n][0]的方案数
        long[][] dp=new long[n][k];
        Arrays.fill(dp[0],1L);
        dp[0][0]=0;
        for(int i=1;i<n;i++){
            long sum=0;
            for(long num:dp[i-1]) sum+=num;
            for(int j=0;j<k;j++){
                dp[i][j]=sum-dp[i-1][j];
                while(dp[i][j]>mod){
                    dp[i][j]%=mod;
                }
            }
        }
        return dp[n-1][0];
    }
}

70%通过率，100%的是数学家吧

发表于 2021-02-25 16:49:24 回复(0)

潇洒哥201803111556731

def mul2Matrix(x,y):
    # 二维矩阵相乘的实现
    ans = [[0 for i in range(2)]for j in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ans[i][j] += (x[i][k]% 1000000007) * (y[k][j] % 1000000007)
    return ans

def mul1Matrix(x,y):
    # 二维矩阵与size为（2*1）的矩阵相乘
    ans = [[0] for j in range(2)]
    for i in range(2):
        for k in range(2):
            ans[i][0] += (x[i][k]% 1000000007) * (y[k][0]% 1000000007)
    return ans

def quickMatrix(m,n):
    # 矩阵快速幂运算实现
    E = [[0 for i in range(2)]for j in range(2)]
    for i in range(2):
        E[i][i] = 1
    while(n):
        if n % 2 != 0:
            E = mul2Matrix(E,m)
        m = mul2Matrix(m,m)
        n >>= 1
    return E

if __name__ == '__main__':
    n, k = map(int, input().split())
    m = [[k-2,k-1],[1,0]]
    x = [[k-1],[0]]
    # 注意考虑特殊情况，若不加此条件，只能通过90%的case
    if n >= 2:
        tmp = quickMatrix(m, n-2)
        print(mul1Matrix(tmp,x)[0][0]%1000000007)
    else:
        print(0)

编辑于 2020-08-27 15:18:35 回复(1)

牛客337519957号

给最高赞的公式贴个图

https://wenku.baidu.com/view/492b9217e53a580216fcfec8.html

发表于 2020-08-23 23:41:52 回复(0)

放弃幻想，准备战斗

K,N=map(int,input().split())
if N<=1 or K<=1:print(0)
elif N==2:print((K-1)%1000000007)

else:print((K-1+(K-2)*(K-2))*(K-1)**(N-3)%1000000007)

感觉是O(n)可解的，但是（K-1)**(N-3)太大了，直接算会出错，基于DP的算法都是每步取模的，和这样直接算然后取模出来结果不同

发表于 2020-06-12 21:46:48 回复(0)

牛客943846962号

n, k = map(int, input().split())
lis = [0]
for i in range(1,n):
    lis.append((k-1)**i-lis[i-1])
print(lis[-1]%1000000007)

发表于 2020-04-24 13:21:14 回复(4)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师 c#工程师数据库工程师猿辅导 2020 大数据开发工程师 Java工程师

上传者：小小

难度：

10条回答 47收藏 6159浏览

通过挑战的用户

LKOne

2022-08-06 14:31:41
WwSsXx

2021-07-28 21:53:47
nash_song

2021-04-06 11:29:48
aqi1221

2021-03-29 16:04:57
瑾明达

2021-03-29 14:31:56

小猿的击鼓传花

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题