首页 > 其他 > 详细

清华集训2016-组合数问题

时间:2020-02-24 18:25:35      阅读:63      评论:0      收藏:0      [点我收藏+]

清华集训2016-组合数问题

题面

Solution

是某个组合数的倍数也就意味着 模上k为0
考虑卢卡斯定理
n拆成k进制\(p1,p2,p3..pa\)
m拆成k进制\(q1,q2,q3..qa\)
模上k等于0,即: \[C_{p1}^{q1}*C_{p2}^{q2}*C_{p3}^{q3}....*C_{pa}^{qa}=0\]
因为k是质数,所以这个式子等于零只需要其中有一项 \(C_i^j\)\(i<j\) 即可
这个直接数位dp就行,递推还是记搜自己喜欢就好
但是最后求到的答案需要减去在没有转成k进制时,组合数本身就等于零的答案
例如 \(C_5^8\) 这种
也就是一个等差数列求和

#include<bits/stdc++.h>
#define ll long long
#define R register
const int mod = 1e9+7;
using namespace std;
namespace IO
{
    template<class T>
    void rea(T &x)
    {
        char ch=getchar();int f(0);x = 0;
        while(!isdigit(ch)) {f|=ch=='-';ch=getchar();}
        while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        x = f?-x:x;
    }
    template<class T>
    T max(T a, T b) {return (a>b?a:b);}
    template<class T>
    T min(T a, T b) {return (a<b?a:b);}
}
using IO::rea;
int k, T, N[100], ln, M[100], lm;
int dp[100][2][2][2];
int dfs(int n, bool lin, bool lim, bool FG)
{
    if(~dp[n][lin][lim][FG]) return dp[n][lin][lim][FG];
    if(!n) return !FG;
    int upn = (lin?N[n]:k-1), upm = (lim?M[n]:k-1);
    int &ans = dp[n][lin][lim][FG]; ans = 0;
    for(R int i = 0; i <= upn; ++i)
        for(R int j = 0; j <= upm; ++j)
            ans = (ans+dfs(n-1, lin&&i==upn, lim&&j==upm, (i<j?0:(FG?1:0))))%mod;
    return ans;
}
int query(ll n, ll m)
{
    memset(dp, -1, sizeof dp);
    ll ans; ln = lm = 0;
    m = min(m, n);
    if(m%2) ans = -(((m+1)/2)%mod*(m%mod))%mod;
    else ans = -((m/2)%mod*((m+1)%mod))%mod;
    for(; n; n /= k) N[++ln] = n%k;
    for(; m; m /= k) M[++lm] = m%k;
    while(lm < ln) M[++lm] = 0;
    ans = ((ans + dfs(ln, 1, 1, 1))%mod+mod)%mod;
    return ans;
}
int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    using IO::max;using IO::min;
    rea(T), rea(k);
    while(T --> 0)
    {
        ll n, m;
        rea(n), rea(m);
        printf("%d\n", query(n, m));
    }
    return 0;
}

清华集训2016-组合数问题

原文:https://www.cnblogs.com/heanda/p/12357974.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!