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

题面

传送门: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;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注