首页 > 试题广场 >

玫瑰花

[编程题]玫瑰花

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

有K种不同的玫瑰花，现在要摆放在N个位置上，要求每种颜色的花至少出现过一次，请问有多少种不同的方案数呢？，因为答案可能很大，你只需要输出它对772235取余后的结果.

输入描述:

输入只有1行，分别有两个整数N,K( 1 <= N <= 50000 , 1 <= K <= 30 )

输出描述:

输出一行表示答案

示例1

输入

3 2

输出

算法知识视频讲解

Timbuktu

import sys
import math
 
if __name__=="__main__":
    line = list(map(int, sys.stdin.readline().strip().split()))
    k=line[1]
    n=line[0]
    value=[i+1 for i in range(k)]
    for j in range(1,k):
        key=[i+1 for i in range(value[j])]
        sum_=0
        for i in range(j):
            key[i]=math.factorial(value[j])/(math.factorial(value[j]-key[i])*math.factorial(key[i]))
            temp1 = key[i]*value[i]%772235
            sum_+=temp1
            sum_=sum_%772235
        temp2 = pow(value[j],n)%772235+772235
        value[j]=int((temp2-sum_)%772235)
    print(value[k-1])

编辑于 2019-08-04 15:55:40 回复(1)

ziyuya

这个题出的不太严谨吧，什么叫每种花至少出现一次？是N个位置的花全部加一起，每种至少出现一次，还是每个位置每种花都至少出现一次？？？

发表于 2020-03-27 17:45:21 回复(0)

zxcv0112358

不会。如果是数学题就直接mma求和那个显式公式了 $\prod_{p_1+p_2+...+p_k=n\\ \ \ \ \ \ \ \ p_i\geq1}\tbinom{n}{p_1,p_2,...p_k}$

Needs["Combinatorica`"]
f[n_Integer, k_Integer] := 
 Sum[Multinomial @@ 
   i, {i, # + ConstantArray[1, k] & /@ Compositions[n - k, k]}]
f[3, 2]

作为编程题,反正你显式公式都出来了，猜一个递推公式问题不大(?,我没猜出来)

一种是 $dp[n][k]=dp[n-1][k-1]*\tbinom{k}{1}+dp[n-1][k]*k$
第一项对应的是说最后1位的颜色在前面未曾出现过，第二项对应的是说最后1位的颜色在前面已经出现过

另一种是 $T(N, K)=K^{N}-\sum_{i=1}^{K-1} \tbinom{K}{i} T(N, i)$
思路很容易懂，把 $k^n$ 个排列做了分类

代码欠着

编辑于 2021-04-08 15:03:07 回复(0)

牛客290824795号

为什么排列组合A(N,K)不对呢或者C(N,K)*A(N,K)

发表于 2021-03-27 23:32:58 回复(0)

TABball

其他朋友都是dp，我写个容斥把

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
typedef long long ll;
const ll mod = 772235;

ll Pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

ll C[35][35];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = Pow(k, n);
    int sign = -1;
    C[0][0] = 1;
    for (int i = 1; i <= k; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    for (int i = 1; i <= k; i++) {
        ans += sign * (C[k][k - i] * Pow(k - i, n) % mod);
        ans = (ans + mod) % mod;
        sign *= -1;
    }
    printf("%lld\n", ans);
    return 0;
}

发表于 2020-04-14 15:39:52 回复(0)

witherlin

import sys
a = sys.stdin.readline().strip().split()
mod = 772235
N = int(a[0])
K = int(a[1])
line1 = [1] * (N)
 
if K > N:
    # 处理 K >N 的情况
    print(0)
else:
    pow = 1
    for i in range(1,K):
        pow *= (i+1)
        line2 = [0] * (N)
        line2[i] = pow
 
        for j in range(i+1,N):
            line2[j] = (i+1) * (line1[j-1] + line2[j-1]) % mod
 
        line1 = line2
 
    print(line1[-1])

动态规划只与上一行有关，于是只保存一行

发表于 2019-09-19 14:13:10 回复(0)

Python

poi201811272000719

python AC solution.

递推公式:

import sys

N,K = list(map(int,sys.stdin.readline().strip().split(' ')))
num_k = [1 for i in range(K)]

def C_N_K(N,K,m=None):
c = 1
K = min(N-K,K)
for i in range(K):
c = c*(N-i)/(i+1)
if m is not None:
return c%m
else:
return c

for i in range(2,K+1):
total_i = pow(i,N,772235)
for j in range(1,i):
c_i_j = C_N_K(i,j,772235)
total_i -= (c_i_j*num_k[j-1])
num_k[i-1] = total_i % 772235

print(int(num_k[-1]))

发表于 2019-09-02 15:25:44 回复(1)

GGGGinóbili

请教一下，这题为什么不能用排列组合思想做？

A(N,K) 从N个位置中选取K个位置放置玫瑰花，然后再对玫瑰花进行组合。我用python算了一下结果不正确了，是因为排列组合有大量重复吗？

发表于 2019-08-29 16:34:31 回复(3)

哈哈欣

请各位大佬帮忙看看，case通过率为15.00%

import java.util.Scanner;

public class rose {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int M=sc.nextInt();
        long a=jiecheng(N);
        long b=jiecheng(M-N);
        long c=a/b;
        System.out.println(c);

    }
    public static long jiecheng(int a){
        long b=1;
        for (int i=1;i<=a;i++){
            b=b*i;
        }
        return b;


    }
}

发表于 2019-08-17 12:18:02 回复(1)

喜酸不喜甜

python 用动态规划内存超限

N,K = map(int,input().split())
dp = [[0]*(K+1) for i in range(N+1)]
dp[0][0] = 0
dp[1][1] = 1
dp[2][1] = 1
for i in range(2,N+1):
    for j in range(2,K+1):
        if i>=j:
            dp[i][j] = j*(dp[i-1][j-1]+dp[i-1][j])
print(dp[N][K]%772235)

编辑于 2019-08-14 21:28:05 回复(0)

hello201903261057737

假设N个位置摆放k种花的方案数为a[N][k]，观察得a[N][k] = k * a[N - 1][k - 1] + k * a[N - 1][k]

利用滚动数组解决

#include<bits/stdc++.h>
using namespace std;
#define M 772235
int main(){
    int N, k;
    cin >> N >> k;
    int a[2][k + 5];
    int pre = 0, cur = 1;
    for(int i = 1; i <= N; i++){
        pre = 1 - i % 2;
        cur = i % 2;
        for(int j = 1; j <= k; j++){
            if(j == 1)a[cur][j] = 1;
            else if(i == j)a[cur][j] = j * a[pre][j - 1] % M;
            else if(i > j)a[cur][j] = j * (a[pre][j - 1] + a[pre][j]) % M;
        }
    }
    cout << a[cur][k] << endl;
    return 0;
}

发表于 2019-08-14 18:37:10 回复(0)

你电瓶车

通过率：15%
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long num = 0;
        if( N == K){
            num = (long)Math.pow(2,N);
            System.out.println(num);
        }else if(N > K){
            num = jie(N)/jie(K)/jie(N - K)*(long)Math.pow(2,K);
            System.out.println(num);
        }else{
            System.out.println(0);
        }
    }
    public static long jie(int n){
        long a = 1;
        while(n >= 1){
            a = a*n;
            n = n - 1;
        }
        return a;
    }
}

发表于 2019-08-08 21:46:48 回复(0)

dwtfukgv

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50000 + 7;
const int mod = 772235;
int n, m;
int dp[maxn][32];
 
int main(){
    scanf("%d %d", &n, &m);
    dp[1][1] = 1;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod * j % mod;
    cout << dp[n][m] << endl;
    return 0;
}

发表于 2019-08-08 21:45:59 回复(8)