洛谷 2822 组合数问题——质因数有关的dp

题目：https://www.luogu.org/problemnew/show/P2822

发现 k 都是一样的。所以可以设dp[ i ][ j ]表示 n<=i，m<=j 的答案。发现它就像一个二维平面，所以可以dp[ i ][ j ]=dp[ i-1 ][ j ]+dp[ i ][ j-1 ]-dp[ i-1 ][ j-1 ]+[ c[ i ][ j ]%k==0 ]；

先写了记录每个数的阶乘含多少个k，然后看减掉之后还有没有k。但这样没考虑k的因数组成k的情况。所以应该把k质因数分解，看减掉的该因数个数与k里的该因数个数的大小关系。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005,M=1e4+5;
int t,k,n[M],m[M],mxn,mxm,mx,a[N][10],dp[N][N],cnt,zs[10],nm[10];
int rdn()
{
    int ret=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return ret;
}
int main()
{
    t=rdn();k=rdn();
    for(int i=1;i<=t;i++)
        n[i]=rdn(),m[i]=rdn(),mxn=max(mxn,n[i]),mxm=max(mxm,m[i]);
    mx=max(mxn,mxm);
    int tmp=k;
    for(int i=2;i<=tmp;i++)
        if(tmp%i==0)
        {
            zs[++cnt]=i;
            while(tmp%i==0)tmp/=i,nm[cnt]++;
        }
    for(int i=1;i<=mx;i++)
        for(int j=1,s=i;j<=cnt;j++,s=i)
            while(s) s/=zs[j],a[i][j]+=s;//数i含有多少第j个质因数 
//    for(int i=1;i<=mx;i++) printf("a[%d]=%d
",i,a[i]);
    for(int i=1;i<=mxn;i++)
    {
        for(int j=1;j<=mxm&&j<i;j++)
        {
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
            bool flag=0;
            for(int o=1,d;o<=cnt;o++)
            {
                d=a[i][o]-a[j][o]-a[i-j][o];
                if(d<nm[o]){flag=1;break;}
            }
            dp[i][j]+=(!flag);
//            printf("dp[%d][%d]=%d(ai-aj-a(i-j)=%d)
",i,j,dp[i][j],
//                a[i]-a[j]-a[i-j]);
        }
        for(int j=i;j<=mxm;j++) dp[i][j]=dp[i][j-1];
//            printf("dp[%d][%d]=%d
",i,j,dp[i][j]);
    }
    for(int i=1;i<=t;i++)
        printf("%d
",dp[n[i]][m[i]]);
    return 0;
}