[HDU6372]Lucas

Link

Solution

根据Lucas Theorem,\binom{n}{m}\mod p=0\Leftrightarrow np进制表示的每一位都\ge mp进制表示的对应位。
对于题目中的np进制数字iHMBB[i][j]=1j的个数就是满足如上条件的j的个数,HMBB的一次方中的1的个数就是p^n-1\ge i\ge j(i,j)数(此处的\ge指每位对应\ge
同理,HMBB^k1的个数就是p^n-1\ge a_1\ge a_2\ge…\ge a_{k+1}的个数。
而每一位是独立的,可以单独计算一位的然后求个幂。
而一位的答案就是以p-1为开头,长度为k+2的不升序列的长度。用组合数计算,可以假设开头再放上一个0,那么就是开头为0,结尾p-1,中间k+1个数的非降序列数。除去开头,后面k+2个数每个数字相对于前面的数字的增量\ge 0,且总的增量为p-1,因此对于增量列出方程

\left\{\begin{aligned}
\sum \Delta_i=&p-1\\
\Delta_i \ge&0
\end{aligned}\right.

方案数为\binom{(p-1)+(k+1)}{k+1}
最终要计算的就是

\begin{aligned}
&\sum_{i=1}^{k}\sum_{j=1}^n \binom{p+i}{i+1}^j
\end{aligned}

Code

#include <bits/stdc++.h>

const int N=2e6,XN=N+11,P=1e9+7;

void M(int &x) {
    ((x>=P) && (x-=P)) || ((x<0) && (x+=P));
}

int Pow(long long base,int v,int P) {
    long long res=1;
    for(;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                break;
            } 
        }
    }
}

int fact[XN],ifact[XN];
int C(int n,int m) {
    return n>=m?1ll*fact[n]*ifact[m]%P*ifact[n-m]%P:0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

//  freopen("input","r",stdin);

    fact[0]=1;
    for(int i=1;i<=N;++i)
        fact[i]=1ll*fact[i-1]*i%P;
    ifact[N]=Pow(fact[N],P-2,P);
    for(int i=N-1;i>=0;--i)
        ifact[i]=1ll*ifact[i+1]*(i+1)%P;

    Prep();
    int T;std::cin>>T;
    while(T--) {
        int c,n,k;std::cin>>c>>n>>k;
        int p=prime[c];
        int Ans=0;
        for(int i=1;i<=k;++i) {
            int v=C(p+i,i+1);
            M(Ans+=v==1?v*n%P:1ll*v*(1ll-Pow(v,n,P))%P*Pow(1-v,P-2,P)%P);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[zoj4056][ICPC 2018 Qingdao Online]Press the Button

Link

Solution

问题最后是求一个长度为t的数轴上有多少对相邻的关键点距离\ge v,关键点是所有ac的倍数的点。
假设a < c
如果a < v则不存在
否则
考虑c的倍数与它后面相邻的a的倍数的距离
根据根据鸽巢原理,至多c步,这个距离就会开始循环
然后把t分成三部分:
不在循环+循环部分+一段没循环完的部分
细节巨多写到脑壳疼
~正解是模拟到{\rm lcm}(a,b),直接判断,然后循环~

Code

const int XN=1e6+11;
void Work() {
    long long v,t,a,b,c,d;
    fin>>a>>b>>c>>d>>v>>t;
    long long Ans=(long long)((t/a)+1)*b+(long long)((t/c)+1)*d-1;
    if(a>v && c>v) {
        if(a>c)
            std::swap(a,c);
        static int us[XN],ut;
        static long long crec[XN],prec[XN];
        ++ut;long long cnt=0,pc=0,py=0;
        for(;;pc+=c) {
            long long x=(pc/a)*a,y=x+a; 
            cnt+=((pc-x)>v)+((y-pc)>v)+(x-py)/a;
            py=y;
            if(us[y-pc]==ut)
                break;
            us[y-pc]=ut;
            crec[y-pc]=cnt;
            prec[y-pc]=py;
        }
        if(t>prec[py-pc]) {
            long long circnt=cnt-crec[py-pc],cirlen=py-prec[py-pc];
            Ans-=circnt*((t-prec[py-pc])/cirlen)+crec[py-pc];
            py+=((t-prec[py-pc])/cirlen-1)*cirlen;
            pc=(py/c+1)*c;
        } else {
            py=pc=0;
        }
        if(pc<=t)
            for(;;pc+=c) {
                long long x=(pc/a)*a,y=x+a;
                Ans-=((pc-x)>v)+(x-py)/a;
                if(y<=t) {
                    Ans-=((y-pc)>v);
                }
                py=y;
                if(pc+c>t)
                    break;
            }
        if(py<t)
            Ans-=(t-py)/a;
    }
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}