原创题目 拼方头 【组合数+记忆化优化】

题目： 

有 n 条木棒，现在从中选 x 根，想要组成一个正 x-1 边形，问有几
种选法？
由于答案较大，输出它 mod 19260817 的答案。
万古神犇 hjr 秒了这道题,现在交给你做，好让方头开心一下。

分析：

此题有两个突破点：

1、既然是用x根木棒去拼x-1边形，那么必然有且仅有一条边是由两根木棒拼成的；

2、且其他边必然是由相同的木棒拼成的，也就是说，一种木棒仅当边数大于x-2时，才有可能成为正多边形中的边长；

于是我们可以一 一枚举满足（2）的木棒，并再通过枚举拼凑第x-1条边；（用cnt[i]表示长度为i的边有多少根）

首先，从cnt[i]根满足（2）的木棒中选出x-2根去拼那x-2条边，有C(cnt[i],x-2)种选择；-------♠

其次，假设a+b=i，那么用a和b去拼第x-1条边，就有cnt[a]*cnt[b]种拼法；但若是a=b，就是C(cnt[a],2)；-----------♥

显然，♠和♥是符合乘法原理的，因此就有：f[i]=C(cnt[i],x-2)*cnt[a]*cnt[b]或是C(cnt[i],x-2)*C(cnt[a],2)；

下面是参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long long mod=19260817;
long long nn,x,a,maxx=0;
long long cnt[1550]={0},p[1550],ex[1550];
long long f[1550]={0};
bool ok[1550];
long long C(long long n,long long m)
{
    if(n<m) return 0;
    if(n==m) return 1;
    if(m==1) return n%mod;
    long long c=1;
    for(long long i=1;i<=m;i++)
        c=(c*(n-i+1)/i)%mod;
    return c;
}
long long cal(long long i)
{
    if(ex[i]) return ex[i];//memorizing search
    memset(p,0,sizeof(p));
    long long an=0;
    for(long long j=1;j<=min(maxx,i);j++)
    {
        if(p[j]) return an;//avoid repeated calculating
        if(j!=i-j)
        {
            an=(an+cnt[j]*cnt[i-j])%mod;
            p[j]=p[i-j]=1;
        }
        else
        {
            an=(an+C(cnt[j],2))%mod;
            p[j]=1;
        }
    }
    return ex[i]=an;
}

int main()
{
//    freopen("ft.in","r",stdin);
//    freopen("ft.out","w",stdout);
    cin>>nn>>x;
    for(int i=1;i<=nn;i++)
    {
        cin>>a;
        maxx=max(maxx,a);
        cnt[a]++;
        if(cnt[a]>=x-2)
            ok[a]=1;
    }
    for(int i=1;i<=maxx;i++)
    {
        if(ok[i])//if it is possible for this edge to be the longest edge
        {
            long long a1=C(cnt[i],x-2);
            long long a2=cal(i);
            f[i]=(a1*a2)%mod;
            //pick x-2 out of cnt[i] for the longest edge
            //how many couple can make up i
            //multiply both above
        }
    }
    long long ans=0;
    for(long long i=1;i<=maxx;i++)
        ans=(ans+f[i])%mod;
    cout<<ans;
    return 0;
}