CF_402F dp+组合数学

时间：2022-07-12 13:18:18

题目链接：http://codeforces.com/problemset/problem/403/D

/**算法分析：

    这道题综合的考察了dp背包思想和组合数学

*/

#include<bits/stdc++.h>

#define MAXN 1050

#define PI acos(-1.0)

#define MOD 1000000007

#define REP(i,n) for(int i=0; i<n; i++)

#define FOR(i,s,t) for(int i=s; i<=t; i++)

#define mem(a,b)  memset(a,b,sizeof(a))

#define show(x) { cerr<<">>>"<<#x<<" = "<<x<<endl; }

#define showtwo(x,y) { cerr<<">>>"<<#x<<"="<<x<<"  "<<#y<<" = "<<y<<endl; }

using namespace std;

int n,k;

int dp[MAXN][];        //dp[i][j]表示把i分成j个不同的数的方案数

int C[MAXN][];         //组合数

long long fact[];      //阶乘

void init_dp()

{

    mem(dp,);

    dp[][] =  ;

    //用0,1背包思想：数字i看成体积为i的物品，放到总体积为n的容器内的方案数

    //实际的dp: dp[d][i][j];但考虑的数的是d是，能够用j个不同的数凑出i的方案数,第一维被优化了

    //转移方程：dp[d][i][j] = dp[d-1][i][j] + dp[d-1][i-d][j-1],分为用与不用d这个数

    for(int d=; d<MAXN; d++)

        for(int i=MAXN-; i>=d; i--)

            for(int j=min(d+,); j>=; j--)

                dp[i][j] = (dp[i][j] + dp[i-d][j-])%MOD;

    mem(C,);

    for(int i=; i<MAXN; i++)

    {

        C[i][] = ;

        for(int j=; j<=min(i,); j++)

            C[i][j] = (C[i-][j]+C[i-][j-])%MOD;

    }

    fact[] = ;

    for(int i=; i<; i++) fact[i] = fact[i-]*i%MOD;

}

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    init_dp();

    int T; cin>>T;

    while(T --)

    {

        int n,k; scanf("%d %d",&n,&k);

        int m = k*(k+)/;

        if(n < m) printf("0\n");

        else

        {

            long long ans = ;

            for(int i=m; i<=n; i++)

                ans = (ans + (long long)C[n-i+k][k]*dp[i][k])%MOD;

            printf("%I64d\n",ans*fact[k]%MOD);

        }

    }

}

相关文章