【GYM102091】2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest F

题意：给一个n求前n行帕斯卡三角中有几个7的倍数。

这玩意其实可以出到任意模数，我们考虑使用Lucas定理，那么C(n,m)=∏C(ni,mi),其中ni,mi为n,m,7进制展开下的数字。不合法方案就是任意ni>=mi的，数位dp硬搞一波。

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int mod =1e9+7;
int dp[2][23];
int bit[23],m;
const int inv=(mod-1)/2+1;
int DP(int pos,bool lim){
    if(pos==m)return 1;
    int& ret=dp[lim][pos];
    if(ret)
        return ret;
    int up=6;
    if(!lim){
        up=bit[pos];
        ret+=1ll*(up+1)*DP(pos+1,lim)%mod;
        up--;
    }
    if(up>=0){
        ret+=1ll*(up+2)*(up+1)*(1ll*inv*DP(pos+1,1)%mod)%mod;
    }
    ret%=mod;
    return ret;
}
int main()
{
    long long n;
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        m=0;
        cin>>n;
        long long tn=n%mod;
        int ans=(tn*(tn+1)%mod*inv%mod+tn+1)%mod;
        while(n){
            bit[m++]=n%7;
            n/=7;
        }
        reverse(bit,bit+m);
        for(int i=0;i<=m;i++){
            dp[0][i]=0;
            dp[1][i]=0;
        }
        printf("Case %d: %d\n",i,(ans-DP(0,0)+mod)%mod);
    }
}

人傻常数大，大哥们可以改成非递归的