题解 P2822 【组合数问题】

· · 题解

分解质因数最好懂。

先把k分解质因数，然后计算C（i，j）里有多少个k的某个质因数，如果个数比k里有的个数小就证明不可能是k的倍数。

计算n！里有多少个质因数p的方法：nump=n/p+n/p^2+n/p^3+n/p^4+...+n/p^k。这里的/是整除，当p^k>n时终止。

用f[i][j]表示C（i，1-j）里有多少个能整除k，g[i][j]表示C（1-i，1-j）里有多少个能整除k。（前缀和思想）

然后用离线的方式先处理好递推，再统一输出结果。

这题很阴险的卡常，O（n*m）的算法不用读入优化会有几个点TLE。

其他详见代码。

#include<cstdio>
#include<algorithm>
using namespace std;
int read()
{
    int in=0,k=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') k=-1; 
    for(;c<='9'&&c>='0';c=getchar())
    in=in*10+c-'0';
    return k*in;
}
const int p[]={0,2,3,5,7,11,13,17,19};
int T,k,n,m,maxn=0,maxm=0,que[20001][2],prime[21],num[21];
int f[2001][2001],g[2001][2001];
void fenjie(int t)//把t分解质因数，prime记录质因数，num记录该质因数的个数。
{
    int i=1;
    while(t>1)
    {
        if(t%p[i]==0)
        {
            if(prime[prime[0]]==p[i]){num[prime[0]]++;t/=p[i];}
            else {prime[++prime[0]]=p[i],t/=p[i];num[prime[0]]=1;}
        }
        else i++;
    }
}
int calc(int t,int k)//计算t！里有多少个质因数k
{
    int ans=0,rec=k;
    while(t>=rec)
    {
        ans+=t/rec;
        rec*=k;
    }
    return ans;
}
bool pd(int i,int j)
{
    int a,b,c;
    for(int t=1;t<=prime[0];t++)
    {
        a=calc(i,prime[t]);//根据组合数计算公式，计算n！，m！和（n-m）！里有多少个质因数prime[i]
        b=calc(j,prime[t]);
        c=calc(i-j,prime[t]);
        if(a-b-c<num[t])return 0;//如果个数不够那么不能整除。
    }
    return 1;
}
int main()
{
    T=read();k=read();
    fenjie(k);
    for(int t=1;t<=T;t++)
    {
        n=read();m=read();
        que[t][0]=n;
        que[t][1]=m;
        if(n>maxn)maxn=n;
        if(m>maxm)maxm=m;
    }
    for(int i=1;i<=maxn;i++)
        for(int j=1;j<=i&&j<=maxm;j++)
        {
            f[i][j]=f[i][j-1]+pd(i,j);
            g[i][j]=g[i-1][min(i-1,j)]+f[i][j];

}//前缀和递推，注意j>i-1的情况

    for(int t=1;t<=T;t++)
    {
        int a=que[t][0],b=que[t][1];
        printf("%d\n",g[a][min(a,b)]);//注意b>a的情况。
    }
    return 0;
}