description
给定 \(n,m,k\)，任意两个长度分别为 \(n,m\) 的 01 串，如果前者所含的 1 的数量严格大于后者，则这两个 01 串是强的，求有多少组强的 01 串，答案模 \(10^k\)
-
\(n,m\leq 10^{15}\)
-
\(m\leq n\leq m+10^4\)
-
\(1\leq k\leq 9\)
-
十测
solution
枚举两个 01 串分别含有多少个 1，答案为 \(\sum\limits_{j=0}^m \sum\limits_{i=j+1}^n \dbinom{m}{j}\dbinom{n}{i}\)。平移 \(i\) 的枚举范围得 \(\sum\limits_{j=0}^m\sum\limits_{i=1}^{n-j} \dbinom{m}{j}\dbinom{n}{i+j}\)。可以将 \(i\) 的枚举上界扩充到 \(n\)，式子值不变，并交换求和顺序得 \(\sum\limits_{i=1}^n\sum\limits_{j=0}^m\dbinom{m}{j}\dbinom{n}{i+j}\)，把 \(\dbinom{m}{j}\) 换成 \(\dbinom{m}{m-j}\)，然后再应用范德蒙德卷积公式得 \(\sum\limits_{i=1}^n \dbinom{n+m}{m+i}=\sum\limits_{i=m+1}^{n+m}\dbinom{n+m}{i}\)。
我们需要较快地求出这个式子在模 \(10^k\) 意义下的值。
对于单个组合数，我们可以使用 exLucas 定理，\(O(2^k+5^k)\) 预处理，\(O(\log(2^k+5^k))\) 求值。但是这个式子的枚举范围是 \(O(n)\) 的，不能接受。
一个十分巧妙的变换是，注意到 \(O(\dfrac{n+m}{2}-m)=O(\dfrac{n-m}{2})\) 并不是很大，而我们应用组合数的性质 \(\sum\limits_{i=0}^n \dbinom{n}{i}=2^n\) 容易得出 \(\sum\limits_{i=\lfloor\frac{n+m}{2}\rfloor}^{n+m} \dbinom{n+m}{i}\) 的值，我们只需要暴力算一下 \(\sum\limits_{i=\lfloor\frac{n+m}{2}\rfloor}^{m} \dbinom{n+m}{i}\) 的值就可以了。
时间复杂度 \(O(T(2^k+5^k+(n-m)\log (2^k+5^k)))\)
算一行一半组合数和的方法见代码。qwq
code
#include<bits/stdc++.h>
using namespace std;
typedef long long E;
inline E ksm(E a,E b,E mod){
E ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
E exgcd(E a,E b,E &x,E &y){
if(!b) return x=1,y=0,a;
E d=exgcd(b,a%b,y,x);
return y-=a/b*x,d;
}
inline E inv(E p,E mod){
if(__gcd(p,mod)!=1) return -1;
E x,y;
E d=exgcd(p,mod,x,y);
return (x%mod+mod)%mod;
}
vector<vector<E>> sum;
int idx;
unordered_map<E,int> id;
E calcu(E n,E p,E pk){ // calcu \frac{n!}{p^x} \bmod p^k (x is the max number s.t. p^x \mid n)
if(!n) return 1;
E t=calcu(n/p,p,pk);
E u=1,L=n%pk,w=id[p]-1;
u=u*sum[w][pk-1]%pk;
t=t*sum[w][L]%pk;
t=t*ksm(u,n/pk,pk)%pk;
return t;
}
inline E solve1(E n,E m,E p,E pk){
E u=calcu(n,p,pk),v=inv(calcu(m,p,pk),pk),w=inv(calcu(n-m,p,pk),pk);
return u*v%pk*w%pk;
}
inline E get(E n,E p){
E t=p,ans=0;
while(t<=n){
ans+=n/t;
t*=p;
}
return ans;
}
vector<pair<E,E>> pd;
inline E crt(E n,E m){
E M=1;
for(auto u:pd) M*=u.second;
E ans=0;
for(auto u:pd){
if(ksm(u.first,get(n,u.first)-get(m,u.first)-get(n-m,u.first),u.second)==0) continue;
E t=solve1(n,m,u.first,u.second)*ksm(u.first,get(n,u.first)-get(m,u.first)-get(n-m,u.first),M)%M;
ans=(ans+t*(M/u.second)%M*inv(M/u.second,u.second)%M)%M;
}
return ans;
}
void init(E p){
sum.clear(); pd.clear(); idx=0;
E x=p;
for(int i=2; i*i<=x; i++){
if(x%i) continue;
E s=1;
while(x%i==0) x/=i,s*=i;
pd.emplace_back(make_pair(i,s));
id[i]=++idx;
}
if(x>1){
id[x]=++idx;
pd.emplace_back(make_pair(x,x));
}
sum.resize(idx);
for(int i=0; i<idx; i++){
E P=pd[i].first;
E s=1;
sum[i].emplace_back(1);
for(int j=1; j<=pd[i].second; j++){
if(j%P) s=s*j%pd[i].second;
sum[i].emplace_back(s);
}
}
}
E a,b,p;
void solve(){
E tmp=1;
while(p--) tmp*=10;
p=tmp;
tmp=log10(tmp);
init(p); // exlucas 预处理
E ans=0;
/*
for(E i=b+1; i<=a+b; i++){ 暴力
ans=(ans+crt(a+b,i));
}
cout<<ans%p<<endl;
ans=0;*/
/*
当 n 为奇数时，2 不存在逆元，不好计算一个组合数的 1/2
此时可以应用组合数的递推公式 C(m,n)=C(m,n-1)+C(m-1,n-1)
变成求上一行（一定是偶数）的一半的和，就好做了
*/
E L=(a+b)/2;
if((a+b+1)&1){
ans=ksm(2,a+b-1,p)+crt(a+b-1,L-1);
ans%=p;
}
else{
ans=ksm(2,a+b-1,p);
L++;
}
if(b+1>L){
for(E i=L; i<=b; i++){
ans=(ans-crt(a+b,i))%p;
}
}
else{
for(E i=b+1; i<L; i++){
ans=(ans+crt(a+b,i))%p;
}
}
ans=(ans%p+p)%p;
printf("%0*lld\n",tmp,ans); // 讨论区看的输出技巧（）
}
int main(){
while(cin>>a>>b>>p) solve();
return 0;
}