锄奸pickad {递推+组合数学}

• 【题目描述】

  两军对垒，敌方派出了N个武将前来叫板，你选定了N个手下，打算和对方决一死战。

  实际上，你并不想赢下这场战斗，因为根据你的眼线汇报，这N个人都已经暗中投奔敌方。所以，你打算让这些人都死在战场上，以绝后患。

  我们把两个武将的战斗简化为战斗力的比较，战斗力高的人赢。你已经知道了对面N个武将的战斗力，分别是Si。

  现在你可以任意指定你的武将的战斗力为任意正整数。指定之后，如果你可以把这些武将和敌方的武将一一对应，使得在所有战斗中你的武将都没有赢，那么这个战斗力方案合法。 剩下的问题，就是有多少种合法方案了。

• 【Sample Input】

  （第一行一个整数T，表示数据组数。接下来T行，每行一个N，然后N个整数Si）

  4

  2 1 2

  9 2 2 2 2 2 2 2 2 2

  3 5 1 2

  5 3 14159 2653589 7 932

  {样例解释}

  对于第一组数据，合法方案分别是：(1,1),(1,2),(2,1)

  对于第二组数据，每个武将的武力值为1或者2，根据乘法原理，答案是2^9=512

• 【Sample Output】

  3

  512

  34

  353127147

• 【数据范围】

  20%的数据，N ≤ 7，Si ≤ 10。

  40%的数据，N ≤ 100，Si ≤ 100。

  70%的数据，N ≤ 200，Si ≤ 10^9。

  100%的数据，N ≤ 1 000，1 ≤ Si ≤ 10^9，T ≤ 5。

【题解】递推+组合数学

首先对S数组从小到大排序，所以现在派出的N个手下一定也是从小到大一一对应。

设f[i]表示前 i 个手下和s1…si的武将比赛合法的方案数。此时手下的武力值取值范围为[1,si]。忽略非法情况后，f[i]=si^i；

接下来扣除非法情况。假设当前已经合法匹配的部分是s1…s[j-1] (j< i)，所以 sj…si 这 i-j+1个数的取值范围是[s[j]+1…s[n]]，取值方案数为 (s[n]-s[j])^(i-j+1)；而这些数的排列方案数为 C(i,j-1)。综上所述得到以下递推式：

f[i]=si^i-∑(f[j-1]* (s[i]-s[j])^(i-j+1)*C(i,j-1)) (1<=j< i)

所以我们只需预处理组合数再按照递推式即可得到答案。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define N 1000
#define mo 1000000007
int T,n,a[N+],b[N+][N+];LL f[N+];
    void init()
    {
        for (int i=;i<=N;++i) b[i][]=;
        for (int i=;i<=N;++i)
            for (int j=;j<=i;++j)
                b[i][j]=(b[i-][j]+b[i-][j-])%mo;
    }
    LL qsm(LL x,int y)
    {
        if (y==) return x;
        LL t=qsm(x,y>>);
        t=t*t%mo;
        if (y&) return (t*x)%mo;
        else return t;
    }
int main() 
{
    freopen("a.in","r",stdin);
    init();
    for (scanf("%d\n",&T);T--;) 
    {
        scanf("%d",&n);
        for (int i=;i<=n;++i) scanf("%d",&a[i]);
        std::sort(a+,a+n+);
        memset(f,,sizeof(f));
        f[]=;
        for (int i=;i<=n;++i)
        {
            f[i]=qsm(a[i],i);
            for (int j=;j<i;++j)
                f[i]=(f[i]-f[j-]*qsm(a[i]-a[j],i-j+)%mo*b[i][j-]%mo+mo)%mo;
        }
        printf("%lld\n",f[n]);
    }
    return ;
}