dtoj4728. 问题求解

求 $sumlimits_{i=1}^n{(imland m)  mod (10^9+7)}$，其中 $land$ 指按位与。

Sol

对于m的每一位，答案即$ sumlimits_{i=0}^n frac{i imes m}{2^x} -2 imes frac{i imes m}{2^{x+1}} $

我们求  $  sumlimits_{i=0}^n frac{i imes m}{2^x} $

类欧几里得即可。

推到见https://www.cnblogs.com/xjqxjq/p/12327729.html 肖神犇好G！

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define mod 1000000007
using namespace std;
ll N,m,ans[166],A; 
ll f(ll a,ll b,ll c,ll n){
    ll nx=n%mod;
    ll v=(((b/c)%mod)*(nx+1))%mod;
    if(!a)return v;
    if(a>=c)return (f(a%c,b%c,c,n)+v+(nx*(nx+1)/2)%mod*((a/c)%mod)%mod)%mod;
    ll T=((__int128)a*n+b)/c-1;
    return ((T+1)%mod*nx%mod-f(c,c-b-1,a,T))%mod;
}
int main(){
    scanf("%lld%lld",&N,&m);
    for(ll i=1,w=1;i<=m;i<<=1,w++){
        if(m&i){
            if(!ans[w])ans[w]=f(m,0,i,N);
            ans[w+1]=f(m,0,i<<1,N);
            A=(A+((ans[w]-2*ans[w+1])*((1LL<<w-1)%mod)%mod))%mod;
        }
    }
    A=(A+mod)%mod;
    cout<<A<<endl;
    return 0;
}