数数(count)

Time Limits: 1000 ms Memory Limits: 262144 KB

Description
ztxz16从小立志成为码农，因此一直对数的二进制表示很感兴趣。今天的数学课上，ztxz16学习了等差数列的相关知识。我们知道，一个等差数列可以用三个数A,B,N表示成如下形式：
$B+A, B+2A, B+3A\cdots B+NA$
ztxz16想知道对于一个给定的等差数列，把其中每一项用二进制表示后，一共有多少位是1，但他的智商太低无法算出此题，因此寻求你的帮助。

Input
第一行输入一个整数T代表数据组数；
接下来T行每行输入三个整数A,B,N；

Output
输出T行，每行一个整数代表答案。

Sample Input

2
4 7 1
5 8 2

Sample Output

3
5

Data Constraint

• 对于30%的数据：
  $1\leq T\leq20 , 1\leq A\leq10000 , 1\leq B\leq10^{16}, 1\leq N\leq10^3$
• 对于60%的数据：
  $1\leq T\leq 20 , 1\leq A\leq10000 , 1\leq B\leq10^{16} , 1\leq N\leq10^9$
• 对于100%的数据：
  $1\leq T\leq20 , 1\leq A\leq10000 , 1\leq B\leq10^{16} , 1\leq N\leq10^{12}$

---

法1

观察一下数列——等差数列，那么它的每一个元素一定对于公差取模恒等于B
设$T(x)=x的二进制中1的个数，F(x)=\sum_{x\equiv B(\mod A)}T(x)$
那么$Ans=F(A*N+B)-F(A)$。
哦哦——好像数位DP啊。嗯，就是它！
设$f[i][j][k][0/1]$表示二进制到第i位，对A取模为j，是否受到上界限制。
方程易推。

#include<cstring>
#include<cstdio>
#define ll long long
#define lowbit(x) (x&(-x))

using namespace std;

ll A,B,n,l,t[64],f[64][10000][2],g[64][10000][2];
int T,d[64];

ll query(ll x){
    for(l=0;x;x>>=1)d[++l]=x&1;
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));g[0][0][1]=1;
    for(int i=0;i<l;i++)for(int j=0;j<A;j++){
        if(g[i][j][0]){
            g[i+1][j][0]+=g[i][j][0];f[i+1][j][0]+=f[i][j][0];
            g[i+1][(j+t[l-i-1])%A][0]+=g[i][j][0];f[i+1][(j+t[l-i-1])%A][0]+=f[i][j][0]+g[i][j][0];
        }
        if(g[i][j][1]){
            if(d[l-i])g[i+1][(j+t[l-i-1])%A][1]+=g[i][j][1],f[i+1][(j+t[l-i-1])%A][1]+=f[i][j][1]+g[i][j][1];
            g[i+1][j][1^d[l-i]]+=g[i][j][1];f[i+1][j][1^d[l-i]]+=f[i][j][1];
        }
    }return f[l][B%A][0]+f[l][B%A][1];
}

int main(){
    scanf("%d",&T);t[0]=1;
    for(int i=1;i<=T;i++){
        ll ans=0;
        scanf("%lld %lld %lld",&A,&B,&n);
        for(int o=1;o<=60;o++)t[o]=t[o-1]*2%A;
        printf("%lld\n",query(A*n+B)-query(B));
    }
}

法2

直接上式子！
考虑二进制中第k位的贡献

$$\begin{align} Ans_k & =\sum_{i=1}^n[Ai+B的第k位为1]\\ & =\sum_{i=1}^n\lfloor\frac{Ai+B}{2^k}\rfloor-2\lfloor\frac{Ai+B}{2^{k+1}}\rfloor \end{align}$$
诶？这个式子很熟悉哦哦—— 类欧
$$Ans_k=f(A,A+B,2^k,n-1)-2f(A,A+B,2^{k+1},n-1)$$

注意一下数据范围就好了——开unsigned ll，让它自然取模，除法优先，总之最后还是算成正确答案的。

#include<cstring>
#include<cstdio>
#define ll unsigned long long

using namespace std;

ll f(ll a,ll b,ll c,ll n){
    if(a==0){
        return (n+1)*(b/c);
    }
    if(a<c && b<c){
        ll m=(a*n+b)/c;
        if(m==0)return 0;
        return n*m-f(c,c-b-1,a,m-1);
    }
    return f(a%c,b%c,c,n)+(n+1)*(b/c)+((n+1)/(1+(n&1)))*(n/(2-(n&1)))*(a/c);
}

int main(){
    int t;scanf("%d",&t);
    for(int i=1;i<=t;i++){
        ll a,b,n,ans=0;scanf("%llu %llu %llu",&a,&b,&n);
        for(ll lo=1;lo<=b+a*n;lo=lo+lo)ans+=f(a,b+a,lo,n-1)-f(a,b+a,lo+lo,n-1)*2;
        printf("%llu\n",ans);
    }
}

【GDOI2018模拟8.8】超级绵羊异或

(File IO): input:shxor.in output:shxor.out
Time Limits: 2000 ms Memory Limits: 524288 KB

Description
求(a) xor (a + b) xor (a + b * 2) xor … xor (a + b * (n - 1))。

Input
第一行有一个整数t 表示测试数据组数，接下来t 行每行三个数n, a, b。

Output
对于每组数据输出一行答案。

Sample Input

2
5 2 5
25 2 52

Sample Output

14
1058

Data Constraint
对于10%的数据， t <= 10, a, n<=1000000, b <= 1000000;
另50%的数据，t <= 100, a, n <= 100000000, b <= 100;
对于100%的数据，t<=10000，a, n<=1000000000， b<=1000000000；

---

呃呃呃
和刚刚那道题不是类似么。考虑第k位的贡献。。。

#include<cstring>
#include<cstdio>
#define ll unsigned long long

using namespace std;

ll f(ll a,ll b,ll c,ll n){
    if(a==0){
        return (n+1)*(b/c);
    }
    if(a<c && b<c){
        ll m=(a*n+b)/c;
        if(m==0)return 0;
        return n*m-f(c,c-b-1,a,m-1);
    }
    return (b/c)*(n+1)+n*(n+1)/2*(a/c)+f(a%c,b%c,c,n);
}

int main(){
    freopen("shxor.in","r",stdin);
    freopen("shxor.out","w",stdout);
    int t;scanf("%d",&t);
    for(int i=1;i<=t;i++){
        ll a,b,n,ans=0;scanf("%llu %llu %llu",&n,&a,&b);
        for(ll lo=1;lo<=(n-1)*b+a;lo=lo+lo){
            ll tmp=f(b,a,lo,n-1)-f(b,a,lo+lo,n-1)*2;
            ans+=(tmp&1)*lo;
        }printf("%llu\n",ans);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}