首页 > 试题广场 > 玫瑰花
[编程题]玫瑰花

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


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


输出描述:
输出一行表示答案
示例1

输入

3 2

输出

6
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)
请各位大佬帮忙看看,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 回复(0)
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)
假设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)
#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 回复(5)

热门推荐

通过挑战的用户