「题解」「清华集训 2016」组合数问题

清华集训 2016 Day 4 T1,一道 $\texttt{Lucas}$ 定理 + 数位 DP 的题目。

题目链接:UOJ 275/清华集训 2016 D4T1。

题目

题目描述

小葱想知道如果给定 $n,m$ 和 $k$,对于所有的 $0\leq i\leq n,0\leq j\leq\min(i,m)$ 有多少对 $(i,j)$ 满足 $C _ i^j$ 是 $k$ 的倍数。

数据范围

变量数据范围
$n,m$$1\leq n,m\leq 10^{18}$
$t$$1\leq t\leq 100$
$k$$1\leq k\leq 100$,且 $k$ 是一个质数

时空限制

题目编号时间限制空间限制
UOJ 275$1\text{s}$$512\text{MiB}$
清华集训 2016 D4T1$1\text{s}$$512\text{MiB}$

题解

思路

一看到 \(n,m\) 那么大,就知道直接算是显然不行的。

我们先对题目条件进行一点点小变换

小变换

\[k\mid\binom{i}{j}\Leftrightarrow\binom{i}{j}\equiv 0\pmod k\]

突然想到 $k$ 为质数,我们可以套用 $\texttt{Lucas}$ 定理。
\[\binom{i}{j}\equiv\binom{\lfloor\frac{i}{k}\rfloor}{\lfloor\frac{j}{k}\rfloor}\binom{i\bmod k}{j\bmod k}\pmod k\]

我们不妨递归套用 $\texttt{Lucas}$ 定理,并且对 $i,j$ 标号,记为 $i _ x,j _ x$。

\[
\begin{aligned}
\binom{i}{j}&\equiv\binom{\lfloor\frac{i}{k}\rfloor}{\lfloor\frac{j}{k}\rfloor}\binom{i\bmod k}{j\bmod k}\pmod k\\
&\equiv\binom{\frac{i-i _ 0}{k}}{\frac{j-j _ 0}{k}}\binom{i _ 0}{j _ 0}\pmod k\\
&\equiv\binom{\frac{\frac{i-i _ 0}{k}-i _ 1}{k}}{\frac{\frac{j-j _ 0}{k}-j _ 1}{k}}\binom{i _ 1}{j _ 1}\binom{i _ 0}{j _ 0}\pmod k\\
&\equiv\binom{\frac{\frac{\frac{i-i _ 0}{k}-i _ 1}{k}-i _ 2}{k}}{\frac{\frac{\frac{j-j _ 0}{k}-j _ 1}{k}-j _ 2}{k}}\binom{i _ 2}{j _ 2}\binom{i _ 1}{j _ 1}\binom{i _ 0}{j _ 0}\pmod k\\
&\cdots\\
&\equiv\prod _ {x=0}^p\binom{i _ x}{j _ x}\pmod k
\end{aligned}
\]

最后得到题目的等价表达式
\[\prod _ {x=0}^p\binom{i _ x}{j _ x}\equiv 0\pmod k\]

考虑进一步的转化

考虑到要满足:
\[\prod _ {x=0}^p\binom{i _ x}{j _ x}\equiv 0\pmod k\]

又因为
\[i _ x,j _ x\in[0,k)\Rightarrow\gcd(k,\binom{i _ x}{j _ x})=1\]

所以这个数只有可能满足
\[\exists x\in[0,p],\binom{i _ x}{j _ x}=0\]


\[\exists x\in[0,p],i _ x<j _ x\]

重新考虑 $i,j$ 的意义,发现实际上是两个 $p+1$ 位的 $k$ 进制数
\[
\begin{cases}
i\to(\overline{i _ pi _ {p-1}\cdots i _ 1i _ 0}) _ k\\
j\to(\overline{j _ pj _ {p-1}\cdots j _ 1j _ 0}) _ k
\end{cases}
\]

于是问题转化为了:求 $n,m$ 范围内满足 $i$ 有至少一位小于 $j$ 的数对 $i,j$ 的个数。

数位 DP

直接求代码比较长,可以转化一下,用总的剪掉不满足条件的($i$ 的每一位都大于等于 $j$)的即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll; //要开 long long
#define MOD 1000000007 //模数

const int MAXSIZE=64;
const ll inv2=500000004; //inv2=(MOD+1)/2

ll n,m,k;
ll dp[MAXSIZE][2][2];
ll a[MAXSIZE],b[MAXSIZE]; //存储两个 k 进制数

int main(void){
    int T;
    scanf("%d%lld",&T,&k);
    while(T--){
        scanf("%lld%lld",&n,&m);
        m=min(n,m);
        reg ll ans=(m%MOD*((m+1)%MOD)%MOD*inv2%MOD+(n-m+1)%MOD*((m+1)%MOD)%MOD)%MOD; //先求总数
        reg int cnta=0,cntb=0;
        while(n){ //求 k 进制数
            a[++cnta]=n%k,b[++cntb]=m%k;
            n/=k,m/=k;
        }
        memset(dp,0,sizeof(dp)); //初始化
        dp[cnta+1][1][1]=1; //初始状态
        for(reg int i=cnta;i;--i)
            for(reg int j=0;j<2;++j)
                for(reg int l=0;l<2;++l){
                    if(!dp[i+1][j][l])
                        continue;
                    reg int Maxx=j?a[i]:k-1,Maxy=l?b[i]:k-1;
                    for(reg int x=0;x<=Maxx;++x)
                        for(reg int y=0;y<=Maxy&&y<=x;++y)
                            dp[i][j&&(x==Maxx)][l&&(y==Maxy)]=(dp[i][j&&(x==Maxx)][l&&(y==Maxy)]+dp[i+1][j][l])%MOD;
                }
        for(reg int i=0;i<2;++i)
            for(reg int j=0;j<2;++j)
                ans=(ans-dp[1][i][j]+MOD)%MOD; //减掉不满足题意的方案
        printf("%lld\n",ans%MOD); //输出答案
    }
    return 0;
}

相关题目