测试46 | 转化

T1:取模下性质。
T2：统计的小技巧。cnt++,cnt--.if(!cnt)id=lst,cnt=1;else cnt+=id==lst?1:-1;
T3:转化问题。大小关系只由最高的不同位决定。

T3发现转化问题方面要注意。

分析，转化。

#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define LL long long
#define il inline
#define rg register
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
#define N 1000010
int n;
int a[N],T[N];
il int MO(int x){return x<n?x:x-n;}
int main(){
    n=read();
    F(i,1,n){
        a[i]=(read()+a[i-1])%n;
        if(a[i]==0){
            printf("%d\n",i);
            F(j,1,i)pf(j);phn;
            return 0;
        }
        if(T[a[i]]){
            printf("%d\n",i-T[a[i]]);
            F(j,T[a[i]]+1,i)pf(j);phn;
            return 0;
        }
        T[a[i]]=i;
    }

}
il int read(){
    int s=0;rg char ch;
    while(ch=getchar(),!isdigit(ch));
    for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
    return s;
}
/*
g++ 1.cpp -g
./a.out
6
5 5 10 3 8 1
*/

View Code

#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define LL long long
#define il inline
#define rg register
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
/*
最多4个1e6,15MB,濒临超限，不要开。
3.5e6max.
*/
#define MAXN 1005
int X[1010],Y[1010],Z[1010],Ct[1010],M,K;
il int max(const int& x,const int& y){return x>y?x:y;}
int main(){
    freopen("2b.in","r",stdin);
    M=read();K=read();
    F(i,1,M)Ct[i]=read();
    F(i,1,M)X[i]=read();
    F(i,1,M)Y[i]=read();
    F(i,1,M)Z[i]=read();
    rg int  S = (1 << K) - 1,id=0,cnt=0,n=0;
    rg LL lst;
    for (rg int i = 1; i <= M; ++i) {
        lst = X[i];
        if(!cnt)id=lst,cnt=1;
        else cnt+=id==lst?1:-1;
        n+=Ct[i];
        for (rg int j = 1; j < Ct[i]; ++j) {
            lst = (lst * Y[i] + Z[i]) & S;
            if(!cnt)id=lst,cnt=1;
            else cnt+=id==lst?1:-1;
        }
    }
    pf(n);
    cnt=0;
    for (rg int i = 1; i <= M; ++i) {
        lst = X[i];
        cnt+=lst==id;
        for (rg int j = 1; j < Ct[i]; ++j) {
            lst = (lst * Y[i] + Z[i]) & S;
            cnt+=lst==id;
        }
    }
    int ans=max(cnt*2-n-1,0);
    printf("%d\n",ans);
}
il int read(){
    int s=0;rg char ch;
    while(ch=getchar(),!isdigit(ch));
    for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
    return s;
}
/*
g++ 2.cpp -g
time ./a.out
4 2
1 1 1 1
1 1 1 2
0 0 0 0
0 0 0 0
*/

View Code

#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define LL long long
#define il inline
#define rg register
#define pf(a) printf("%d ",a)
#define PF(a) printf("%lld ",a)
#define phn puts("")
using namespace std;
int read();
/*
调试信息
*/
#define N 200010
int n,m;
const int mod=1e9+7;
int a[N],b[N],c[N],val[N];
il int cmp(const int& x,const int& y){
    return b[x]>b[y];
}
il void MO(int &x){x=x>=mod?x-mod:x;}
il void work1(){
    F(i,1,n)a[i]=read(),c[i]=i;
    int ed=(1<<m)-1;
    F(j,0,ed){
        F(i,1,n)b[i]=a[i]^j;
        sort(c+1,c+n+1,cmp);
        F(i,1,n){
            MO(val[c[i]]+=(i-1)*(i-1)%mod);
        }
    }
    int ans=0;
    F(i,1,n)ans^=val[i];
    printf("%d\n",ans);
}
int tr[6100010][2],tot,cnt[6100010];
il void insert(int x){
    int p=0,t=0;
    for(int i=m-1;~i;--i){
        t=(x>>i)&1;
        if(!tr[p][t])tr[p][t]=++tot;
        p=tr[p][t];++cnt[p];
    }
}
int f[35],top;
il void ask(int id){
    int x=a[id];int p=0,t=0;top=0;LL w;
    for(int i=m-1;~i;--i){
        t=(x>>i)&1;
        if(tr[p][!t]){
            w=f[++top]=cnt[tr[p][!t]];
            MO(val[id]+=w*w%mod*(1<<(m-1))%mod);
        }
        p=tr[p][t];
    }
    LL sum=0;
    F(i,1,top){
        MO(val[id]+=2ll*f[i]*sum%mod*(1<<(m-2))%mod);
        sum+=f[i];
    }
}
int main(){
    n=read();m=read();
    F(i,1,n)a[i]=read(),insert(a[i]);
    F(i,1,n)ask(i);
    int ans=0;
    F(i,1,n)ans^=val[i];
    printf("%d\n",ans);
}
il int read(){
    int s=0;rg char ch;
    while(ch=getchar(),!isdigit(ch));
    for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
    return s;
}
/*
g++ 3.cpp -g
./a.out
6 3
0 2 3 4 6 7
*/

View Code

$ \sum\limits_{i=1}^{n} $