Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)F3

题意:n个数字1-m,问取k个组成的set方案数

题解:假设某个数出现k次,那么生成函数为\(1+x+...+x^k\),那么假设第i个数出现ai次,结果就是\(\sum_{i=1}^m(1+x+...+x^{a_i})\),第k项即为答案,启发式合并fft即可

组合(即set):普通生成函数.排列:指数型生成函数

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

//#include <bits/extc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define mt make_tuple

//#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1009

#define ld long double

//#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define ull unsigned long long

#define bpc __builtin_popcount

#define base 1000000000000000000ll

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

#define mr mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=mul(ans,a,c);a=mul(a,a,c),b>>=1;}return ans;}

using namespace std;

//using namespace __gnu_pbds;

const ld pi = acos(-1);

const ull ba=233;

const db eps=1e-5;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=200000+10,maxn=2000000+10,inf=0x3f3f3f3f;

struct cd{

    ld x,y;

    cd(ld _x=0.0,ld _y=0.0):x(_x),y(_y){}

    cd operator +(const cd &b)const{

        return cd(x+b.x,y+b.y);

    }

    cd operator -(const cd &b)const{

        return cd(x-b.x,y-b.y);

    }

    cd operator *(const cd &b)const{

        return cd(x*b.x - y*b.y,x*b.y + y*b.x);

    }

    cd operator /(const db &b)const{

        return cd(x/b,y/b);

    }

}a[N<<3],b[N<<3];

int rev[N<<3];

void getrev(int bit)

{

    for(int i=0;i<(1<<bit);i++)

        rev[i]=(rev[i>>1]>>1) | ((i&1)<<(bit-1));

}

void fft(cd *a,int n,int dft)

{

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

        if(i<rev[i])

            swap(a[i],a[rev[i]]);

    for(int step=1;step<n;step<<=1)

    {

        cd wn(cos(dft*pi/step),sin(dft*pi/step));

        for(int j=0;j<n;j+=step<<1)

        {

            cd wnk(1,0);

            for(int k=j;k<j+step;k++)

            {

                cd x=a[k];

                cd y=wnk*a[k+step];

                a[k]=x+y;a[k+step]=x-y;

                wnk=wnk*wn;

            }

        }

    }

    if(dft==-1)for(int i=0;i<n;i++)a[i]=a[i]/n;

}

int c[N];

struct info{

    vi v;

    int id;

    bool operator <(const info&rhs)const{

        return v.size()<rhs.v.size()||(v.size()==rhs.v.size()&&id<rhs.id);

    }

};

set<info>s;

int main()

{

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

    for(int i=1,x;i<=n;i++)scanf("%d",&x),c[x]++;

    for(int i=1;i<=m;i++)if(c[i])

    {

        info te;te.v.clear();te.id=i;

        for(int j=0;j<=c[i];j++)te.v.pb(1);

        s.insert(te);

    }

    while(s.size()>=2)

    {

        info x=*s.begin();s.erase(s.begin());

        info y=*s.begin();s.erase(s.begin());

        int p=x.v.size(),q=y.v.size();

        int sz=0;

        while((1<<sz)<=p+q)sz++;

        getrev(sz);

        int len=(1<<sz);

        for(int i=0;i<len;i++)

        {

            a[i]=(i<p?x.v[i]:0);

            b[i]=(i<q?y.v[i]:0);

        }

        fft(a,len,1);fft(b,len,1);

        for(int i=0;i<len;i++)a[i]=a[i]*b[i];

        fft(a,len,-1);

        x.v.clear();

        for(int i=0;i<len;i++)x.v.pb(((ll)(a[i].x+0.5))%mod);

        while(x.v.size()&&x.v.back()==0)x.v.pop_back();

        s.insert(x);

    }

    printf("%d\n",s.begin()->v[k]);

    return 0;

}

/********************

********************/

巴特西

Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)F3 - Lightsabers (hard)

最新文章

热门文章