题面

传送门：UOJ

Solution

这题的数位DP好蛋疼啊qwq 好吧，我们说回正题。首先，我们先回忆一下LUCAS定理：

$C_n^m \equiv C_{n/p}^{m/p} \times C_{n\%p}^{m\%p} (\%p)$

我们仔细观察这个定理，就可以发现一个事实：LUCAS定理本质上是在对n，m两个数做K进制下的数位分离所以说，LUCAS定理我们可以这样表示：

$C_n^m \equiv \prod C_{a_i}^{b_i}$

（ai与bi为K进制拆分后的两个数的每一位数，若一个数的位数不足另一个数，则以前导零填充）我们要判断一个$C_n^m$是否能被K整除，只需要保证其中一个$C_{a_i}^{b_i}$能被K整除（即同余K为零）就好。又因为K为质数，且ai，bi均小于K，所以说我们要使得$C_{a_i}^{b_i}$为0，必须有$b_i$>$a_i$ . . 所以说，问题就变为了对于有多少个$(i,j)$使得$j$中某一位$>i$ 这个新的问题显然可以用数位DP来解决。在这里，我使用记忆化搜索来写（用记忆化可以减少讨论数）考虑这样设状态： 设$f[x][0/1][0/1][0/1][0/1][0/1]$表示填到第$x$位， i是否卡上界n，j是否卡上界m，j是否卡上界 $(j<i)$,上一位是否为前导零（这道题不需要，但是为了模板完整性。我还是写上去了），之前是否有某一位达成需求，之后可以达成的总共的可行方案数转移非常好讨论，我们只需要注意一下j的上界是两个限制的最小值就好。我是这样写转移的：

for(int i=0;i<=(limit1==true?l1[to]:K);i++)
    {
        int t_j=(limit2==true?l2[to]:K);
        t_j=(limit3==true?min(i,t_j):t_j);
        for(int j=0;j<=t_j;j++)
        {
            t_ans+=dfs(to+1,limit1==true and i==l1[to],limit2==true and j==l2[to],limit3==true and j==i,zero==true and i==0,OK==true or j>i);
            t_ans%=poi;
        }
    }

这样子写，看起来时间复杂度是 $O(T*n^2*2^5)$ 但是因为我们会少讨论很多没有意义的情况，所以说能跑得过去。确切复杂度我不会算qwq 还请dalao们指点

Code

//BZOJ 4737: 组合数问题
//Jan,14th,2019
//LUCAS定理的运用+鬼畜数位DP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int poi=1000000007;
const int N=70;
long long f[N][2][2][2][2][2];//到i位，底数卡不卡n，指数卡不卡m，指数卡不卡底数，zero，OK
int n,l1[N],l2[N],K;
long long dfs(int to,bool limit1,bool limit2,bool limit3,bool zero,bool OK)
{
    if(f[to][limit1][limit2][limit3][zero][OK]>=0) return f[to][limit1][limit2][limit3][zero][OK];
    long long t_ans=0;
    if(to==n+1)
    {
        if(OK==true)
            t_ans=1;
        return f[to][limit1][limit2][limit3][zero][OK]=t_ans;
    }
    for(int i=0;i<=(limit1==true?l1[to]:K);i++)
    {
        int t_j=(limit2==true?l2[to]:K);
        t_j=(limit3==true?min(i,t_j):t_j);
        for(int j=0;j<=t_j;j++)
        {
            t_ans+=dfs(to+1,limit1==true and i==l1[to],limit2==true and j==l2[to],limit3==true and j==i,zero==true and i==0,OK==true or j>i);
            t_ans%=poi;
        }
    }
    return f[to][limit1][limit2][limit3][zero][OK]=t_ans;
}
int main()
{
    int T=read();K=read();
    for(;T>0;T--)
    {
        n=0;
        long long num1=read(),num2=read();
        num2=min(num1,num2);//防止m>n

        while(num1!=0)
            l1[++n]=num1%K,num1/=K;
        for(int i=1;i<=n;i++)
            l2[i]=num2%K,num2/=K;
        reverse(l1+1,l1+1+n);
        reverse(l2+1,l2+1+n);
        memset(f,0x80,sizeof f);
        K--;
        dfs(1,true,true,true,true,false);
        K++;

        printf("%lld\n",f[1][true][true][true][true][false]);
    }
    return 0;
}

[UOJ 275/BZOJ4737] 【清华集训2016】组合数问题

题面

Solution

$C_n^m \equiv C_{n/p}^{m/p} \times C_{n\%p}^{m\%p} (\%p)$

$C_n^m \equiv \prod C_{a_i}^{b_i}$

Code