403 D. Beautiful Pairs of Numbers

51 阅读 0 评论 34 点赞

我是靠谱客的博主乐观眼神，最近开发中收集的这篇文章主要介绍403 D. Beautiful Pairs of Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*
 题意:给定n和k,问满足1<=a1<=b1<a2<=b2<a3<=b3<...<ak<=bk<=n,并且b1-a1,b2-a2,b3-a3...bk-ak互不相同的组数.
 假设x1=b1-a1,x2=b2-a2,x3=b3-a3,...,xk=bk-ak
 则可以得到a1+x1+...+xk+k-1<=n,我们要求它的非负整数解
 也就是要求x1+x2+...+xk<=n-a1+1的正整数解
 我们通过枚举a1求解.
 那问题的实质就变成了求x1+x2+...+xk<=n的互不相同的正整数解
 注意到n的范围只有1000,所以k一定小于46.
 设计dp方程:dp[i][j][k]:前i个数,和为j,并且最后一个是k的方法数(默认递增排序)
 则dp[i][j][k]=sum(dp[i-1][j-k][p]),其中p<k.
 这样的复杂度是50*n^3,不仅超时,而且超内存.
 注意到dp方程每次只是取一个前缀和,我们可以只用一个sum数组来对dp值进行更新和维护,并且将复杂度降到50*n^2
 并且在确定了sum[i][k][k](前i个数,和为k,最大值小于等于k的方法数)后,我们需要乘上一个组合数,来安排解之间的空间
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define LL long long

//int  dp[55][1111][1111];
int  sum[46][1001][1001];
//int  g[55][1111];
int  f[55][1111];
int  C[1111][1111];
LL  fac[55];
const int MOD = 1000000007;

void init()
{
    C[0][0]=1;
    for(int i=1;i<1001;i++)
    {
        C[i][0]=1;
        for(int j=1;j<1001;j++)
        {
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
        }
    }
    //dp[0][0][0]=1;
    sum[0][0][0]=1;
    for(int i=1;i<46;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            for(int k=1;k<=1000;k++)
            {
                if(k>j)  break;
                //dp[i][j][k] = sum[i-1][j-k][min(k-1,j-k)];
                int tmp = sum[i-1][j-k][min(k-1,j-k)];//这句很关键.1111100000
                /*
                for(int p=0;p<k;p++)
                {
                    if(j-k<p)   break;
                    dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-k][p])%MOD;
                }
                 */
                sum[i][j][k] = (sum[i][j][k-1] + tmp)%MOD;
            }
        }
    }
    
    //printf("%lld %lldn",dp[1][1][1],dp[1][2][2]);
    
    fac[0]=1;
    for(int i=1;i<55;i++)
    {
        fac[i]=(fac[i-1]*i)%MOD;
    }

    for(int i=1;i<46;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            for(int k=i*(i+1)/2;k<=j;k++)
            {
                LL  tmp = ((LL)C[j-k+i-1][i-1]*(LL)sum[i][k][k])%MOD;
                f[i][j] = (f[i][j] + tmp)%MOD;
            }
            f[i][j] = ((LL)f[i][j]*fac[i])%MOD;
        }
    }
    
    //printf("%lld %lldn",f[2][4],f[2][3]);
}

void solve(int n,int k)
{
    LL  ans = 0;
    for(int i=n;;i--)
    {
        if(k*(k+1)/2>i)
            break;
        ans = (ans + f[k][i])%MOD;
    }
    printf("%lldn",ans);
}

int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if(k>=46)
        {
            printf("0n");
            continue;
        }
        solve(n,k);
    }
    return 0;
}