UOJ 275. 【清华集训2016】组合数问题

组合数 $C_n^m $表示的是从 \(n\) 个物品中选出 \(m\) 个物品的方案数。举个例子，从$ (1,2,3)(1,2,3)$ 三个物品中选择两个物品可以有 \((1,2),(1,3),(2,3)\) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数$ C_m^n$的一般公式：
\[ C_n^m=\frac{n!}{m!(n-m)!} \]
其中 \(n!=1×2×?×n\)。（额外的，当 n=0n=0 时， n!=1n!=1）

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

答案对 \(10^9+7\) 取模。

输入格式

第一行有两个整数 \(t,k\)其中 \(t\) 代表该测试点总共有多少组测试数据。

接下来 \(t\) 行每行两个整数 \(n,m\)。

输出格式

\(t\) 行，每行一个整数代表所有的 \(0\leq i\leq n,0\leq j\leq \min \left \{ i, m \right \}\) 中有多少对$ (i,j)\(满足\)C_i^j$是 \(k\) 的倍数。

限制与约定

对于\(100\%\) 的测试点， \(1\leq n,m\leq 10^{18},1 \leq t,k\leq 100\)，且 \(k\) 是一个质数。

\(\\\)
首先考虑使用卢卡斯定理：
\[ \text{Lucas}(n,m)\bmod k=\text{Lucas}(\frac{n}{k},\frac{m}{k})\cdot\binom{n\%k}{m\%k}\bmod k \]
迭代过程中只要有一位上的\(\binom{n\%k}{m\%k}=0\)那么最后的组合数就是\(k\)的倍数。当\(n<k,m<k\)时，只有\(n<m\)的情况下：\(\binom{n}{m}=0\)。

我们将\(n,m\)写成\(k\)进制的数，然后做数位\(DP\)。先不考虑\(j\leq i\)的限制的话要好做一些，然后在减掉\(j>i\)的情况（这部分显然为0）就好了。

代码（小心爆\(long\ long\)）：

#include<bits/stdc++.h>
#define ll long long

using namespace std;
inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;
ll n,m,k;
ll A[100],B[100];

int d;
#define pr pair<ll,ll>
#define mp(a,b) make_pair(a,b)

pr f[100][2][2];
pr dfs(int v,int flag1,int flag2) {
    if(v<0) return mp(0,1);
    if(f[v][flag1][flag2].first!=-1) return f[v][flag1][flag2];
    int u1=(!flag1)?k-1:A[v],u2=(!flag2)?k-1:B[v];
    ll ans0=0,ans1=0;
    pr now;
    for(int i=0;i<=u1;i++) {
        for(int j=0;j<=u2;j++) {
            now=dfs(v-1,flag1&&i==u1,flag2&&j==u2);
            if(i<j) {
                (ans0+=1ll*now.first+now.second)%=mod;
            } else {
                (ans0+=now.first)%=mod;
                (ans1+=now.second)%=mod;
            }
        }
    }
    f[v][flag1][flag2]=mp(ans0,ans1);
    return mp(ans0,ans1);
}

ll cal(ll l,ll r) {return 1ll*(l+r)*(r-l+1)/2%mod;}

int main() {
    int T=Get();
    k=Get();
    while(T--) {
        n=Get(),m=Get();
        d=0;
        ll mx=max(n,m);
        while(mx) {
            d++;
            mx/=k;
        }
        d--;
        ll x=n;
        for(int i=0;i<=d;i++) {
            A[i]=x%k;
            x/=k;
        }
        x=m;
        for(int i=0;i<=d;i++) {
            B[i]=x%k;
            x/=k;
        }
        for(int i=0;i<=d;i++)
            for(int a=0;a<=1;a++)
                for(int b=0;b<=1;b++) f[i][a][b]=mp(-1,-1);
        pr ans=dfs(d,1,1);
        ans.first=(ans.first-cal(max(1ll,m-n)%mod,m%mod)+mod)%mod;
        cout<<ans.first<<"\n";
    }   
    return 0;
}

UOJ 275. 【清华集训2016】组合数问题

原文：https://www.cnblogs.com/hchhch233/p/10753140.html