P6669[清华集训2016] 组合数问题（题解）

· · 题解

Description.

求

\sum_{i=1}^{n}\sum_{j=1}^{\min(i,m)}[k|C_i^j]

P.S.

前置知识： Lucas 定理

（摘自百度百科。详细证明及实现方法左传模板

此篇题解假设读者已经会了 Lucas 定理以及实现方法。

Solution.

我们首先县观察数据范围，发现 k 是一个质数。
题目名字又叫组合数问题，那我们能第一时间反应出来这是道 Lucas 的题目。
我们分析一下 Lucas 是如何求组合数 \text{mod}\ k 结果的。 

inline int C(int n,int m)
{
    if(m>n) return 0;//这个fac是阶乘数组
    else return 1ll*fac[n]*qpow(fac[m],k-2)%k*qpow(fac[n-m],k-2)%k;
}
inline int lucas(int n,int m)
{
    if(m==0) return 1;
    else return 1ll*C(n%k,m%k)*lucas(n/k,m/k)%k;
}

这就是笔者的 Lucas 代码，（写的丑，请轻喷。
我们发现其实 Lucas 定理就是把组合数的 n 和 m 一遍一遍对 k 取模，把所有取模后的余数的组合数乘起来。
感觉这个方式有点似曾相识，我们在做进制转换时也时这样做的。
所以 Lucas 定理的本质就是把 n 和 m 转化成 k 进制，然后把每进制位上的数位求组合数，最后把所得到的组合数乘起来。
同时我们又发现，k 进制的每一个进制位上的数都小于 k。
又根据组合数的定义：

C_n^m=\frac{n!}{m!(n-m)!}

所以当 m\le n<k 时，C_n^m 肯定没有 k 这个因数。
那么我们是怎么让它 \text{mod}\ k 等于 0 的呢？
我们手模一组样例或者仔细观察一下上面的代码就可以知道，当 m>n 时组合数就为 0 了。
当 m<=n 时 C_n^m\ \text{mod}\ k \not = 0 ， 当 m>n 时组合数一直为 0。
所以C_n^m\ \text{mod}\ k=0的充分必要条件是，把 n 和 m 转化成 k 进制后存在一位，使得 n 在这位上的数值小于 m 在这位上的数值。
所以最后我们直接对 n 和 m 进行一个数位 dp，就可以得到最后的答案了。

完结撒花。

Coding.

注意，这篇代码为了使实现变得简单，用了一个小小的容斥
也就是说，组合数对 k 取模模为 0 的数等于总数减去对 k 取模答案不为 0 的方案数。 

//也请让我相信，你一直以来所相信的事吧——“活着是一件很美好的事”
//只要记住你的名字 不管你在世界的哪个地方 我一定会去见你
//我现在依然喜欢着你，但我们就算是来往一千封邮件，心却不可能接近哪怕一厘米
//嗯，那样的话，你就再努力一次试试吧！别在这种地方畏畏缩缩的！别对自己说谎！再努力一次吧
//拜托了 请把力量借给软弱的我 给我从这里再度起身迈步的力量
//虽然灯塔已经失去了光明…… 但是 只要有你的那首歌在 就一定能将那些人再次导向此方
//小时候曾认为这个世界会更加的单纯简单，没有赢不了的比试，努力就会有回报，认为这世上一切皆有可能。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=1000000007;int t,k,n,m,dp[105][2][2],cnt1,a[105],cnt2,b[105];
inline int dfs(int x,int lim1,int lim2)
{//数位dp，用的记搜，x表示当前搜到了第几位，lim1表示当前n是否顶到了上界，lim2表示m
    if(!x) return 1;else if(dp[x][lim1][lim2]!=-1) return dp[x][lim1][lim2];
    //边界条件，或者记忆化
    int ed1=lim1?a[x]:k-1,ed2=lim2?b[x]:k-1,res=0;
    //ed表示end，即当前这一位能取的最大值
    for(int i=0;i<=ed1;i++) for(int j=0;j<=i&&j<=ed2;j++) res=(res+dfs(x-1,lim1&&i==ed1,lim2&&j==ed2))%P;
    //直接dp，数位dp模板
    return dp[x][lim1][lim2]=res;//记忆化
}
signed main()
{
    for(scanf("%lld%lld",&t,&k);t--;)
    {
        scanf("%lld%lld",&n,&m),m=min(n,m),cnt1=cnt2=0,memset(dp,-1,sizeof(dp)),memset(b,0,sizeof(b));//多组数据清零
        int r=(((m+1)%P*((m+2)%P))%P*500000004%P+(n-m)%P*((m+1)%P)%P)%P;
        //r表示总数，这个500000004是2%(1e9+7)的乘法逆元，懒得打一个快速幂了QAQ
        {while(n) a[++cnt1]=n%k,n/=k;}{while(m) b[++cnt2]=m%k,m/=k;}
        //把n和m按照k进制展开
        printf("%lld\n",(r-dfs(cnt1,1,1)+P)%P);//减去答案不为0的答案
    }
    return 0;
}