NTT 数学 组合数 生成函数    发布于 2019-10-12   158人围观   0条评论

图片标题

题解

首先声明……其实我们的答案跟Wi没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i(niS)!,然后剩下的位置任意涂色,一共还剩n-i*S个位置,每个位置有m-i种颜色选择,所以方案数为(mi)niS
我们记fi=Cmin!(S!)i(niS)!(mi)niS
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候,我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设ansi为恰好i种颜色都恰好出现k次,由容斥原理有:
ansi=j=imin(m,n/S)(1)jiCjifjj

查看更多
NTT 数学 组合数    发布于 2019-10-12   194人围观   0条评论
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
    fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
    for(int i = 2;i <= x;++i){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
    return;
}
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
    len = 1;lg = 0;
    for(len = 1;len < k;len <<= 1,lg++);
    for(int i = 0;i < len;++i)
        rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
    for(int i = 0;i < len;++i){
        if(i < rev[i])
            swap(a[i],a[rev[i
查看更多
生成函数 NTT    发布于 2019-09-26   699人围观   0条评论

题解

如果你曾经经过大量的FFT/NTT的生成函数训练,应该一眼能够看出这道题一定是个多项式卷积用NTT优化……

如果是相加的话,我们可以直接设多项式S = Σaixi,(生成函数在这)其中ai表示数字i出现过多少次。

如果我们是选2个数的话,对于每一个和的方案数,很明显就是将S卷上S,然后取对应多项式项的系数即为方案数。

因为这个题是乘积,而且对于乘积还有对质数m取模操作,所以我们不能简单的按照上面的方法进行生成函数构造。

如何解决乘积问题呢?

我们知道多项式FFT/NTT都是建立在指数(下标)相加的基础上(也就是普通的多项式乘法的法则)进行的,所以我们想能不能把乘积变成加法,这样就可以按照经典套路进行生成函数构造了。

想了一下,取对数貌似可以把乘法变成加法来算了……

但是因为此处还是对质数m取模之后结果的统计,而且NTT也不支持浮点数,所以我们需要考虑在模意义下的对数,也就是离散模对数。

如何处理离散模对数呢……这里如果不了解的话就需要补一下基础的数论知识了。

这里我们需要求m的原根,求法也非常简单,直接暴力枚举的每个数,看对于每个质数pi | (m-1),是否g的(m-1)/pi次方mod m等于1,如果等于则说明不是原根,否则说明是原根,原根通常非常小,所以不用担心会在处理原根的时候TLE。

运用原根,我们可以把每个数在mod m意义下的离散模对数求出来,然后就变成正常的多项式卷积啦!

于是这个时候我们就可以用NTT来做啦。

但是由于要选N次,而N的数据范围到了1e9次,所以我们不能直接暴力NTT,要用快速幂的思想对多项式进行快速幂形式的卷积操作。

这里要注意每一次卷积完成的时候(IDNT之后),我们只是正常的进行了一次多项式卷积,统计答案的时候还是有问题的,因为指数并不能取模,所以每一卷积,都会有答案落在[m-1,2*m-2]上,我们要把这一区域上的答案对应地加到前面[0,m-2]上(对应了题目中的乘积取模操作)。

总时间复杂度为O(nlog2n)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxm = 16005;
typedef long long ll;
const ll gf = 3;
int n,m,x,s;
ll tmp;
int sq;
const ll mod = 1004535809;
ll f
查看更多