T1 与(and)

Solution

从最高位开始搜，假设当前搜到i位，如果有两个以上的数第i位是1，那么Answer的第i位肯定是1，把这位不是1的数都去掉，继续往下搜，在这个过程中更新Answer。

#include
    
     #include
     
      #include
      
       inline long long read(){    long long x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 300005long long n,a[MN],cnt,ans;int main(){    freopen("and.in","r",stdin);    freopen("and.out","w",stdout);    n=read();    register int i,j,k;    for(i=1;i<=n;i++) a[i]=read();    for(j=30;j>=0;j--){        cnt=0;        for(i=1;i<=n;i++) if((a[i]>>j)&1) cnt++;        if(cnt>=2){            for(i=1,k=0;i<=n;i++) if((a[i]>>j)&1) a[++k]=a[i];            ans+=(1<

T2 计数(count)

题目在这

Solution

记f[i][j]表示有i位、各位数之和是j的数量。

显然，前n位之和与后n位之和相等的数和奇数位之和与偶数位之和相等的均有

\[ \sum_{i=0}^M f_{n,i} \ \ \ \ \ \ (其中M表示n位数的各位数之和的最大值） \]

把两者相加，再减去同时满足两个条件的数的数量。

我们设前n位的奇数位和为a，偶数位为b；后n位的奇数位和位c，偶数位和为d。

所以 $ a+b=c+d $并且 $ a+c=b+d $ 所以 $ a=c $ 并且$ b=d$。

那么这部分的方案数等于：

\[ \sum_{i=0}^M f_{n/2,i}* \sum_{j=0}^M f_{(n+1)/2,j} \]

#include
    
     #include
     
      #include
      
       #include
       
        #define mod 999983int n,cc,s[15],ans,a,b;int f[1005][9005];char S[15];inline void add(int &x,long long y){x+=y;while(x>=mod) x-=mod;}inline void minus(int &x,long long y){x-=y;while(x<0) x+=mod;}int main(){    freopen("count.in","r",stdin);    freopen("count.out","w",stdout);    scanf("%d%s",&n,S+1);    cc=strlen(S+1);    register int i,j,k;    for(i=1;i<=cc;i++) s[i]=S[i]-'0';    std::sort(s+1,s+cc+1);    f[0][0]=1;int MAX=s[cc]*n;    for(i=0;i
        
         <=MAX;j++)if(f[i][j]>0){        for(k=1;k<=cc;k++) add(f[i+1][j+s[k]],f[i][j]);    }    for(i=0;i<=MAX;i++) add(ans,((2LL)*f[n][i]*f[n][i])%mod);    int len1=n>>1,len2=n+1>>1;MAX=s[cc]*len2;    for(i=0;i<=MAX;i++){        add(a,(1LL*f[len2][i]*f[len2][i])%mod);        add(b,(1LL*f[len1][i]*f[len1][i])%mod);    }    printf("%d\n",(ans-(1LL*a*b)%mod+mod)%mod);    return 0;}

T3 三角形(triangle)

题目在这

Solution

题目即判断链上是否存在a[x]+a[y]>a[z]

将链上的权值取出来排序，只需要判断是否有b[i]+b[i+1]>b[i+2]

如果都不满足，则有b[i+2]>=b[i]+b[i+1]，则b[i]至少会以斐波那契数列增长的速度增长

那么如果链的长度超过一定值（O(log 2^31)级别），必然存在合法的三元组

如果不超过，暴力判断即可

注意：会爆int

#include
    
     #include
     
      #include
      
       inline long long read(){    long long x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005int n,m,a[MN],dep[MN],f[MN];int Sort[MN],cnt;struct edge{    int to,nex;}e[MN<<1];int hr[MN],pin;inline void ins(int f,int t){    e[++pin]=(edge){t,hr[f]};hr[f]=pin;    e[++pin]=(edge){f,hr[t]};hr[t]=pin;}inline void dfs(int fa,int x){    f[x]=fa;dep[x]=dep[fa]+1;register int i;    for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa)dfs(x,e[i].to);}inline bool solve(int x,int y){    cnt=0;    while(x!=y){        if(dep[x]
       
        50) return 1;    }    Sort[++cnt]=a[x];    if(cnt>50) return 1;    std::sort(Sort+1,Sort+cnt+1);    for(register int i=3;i<=cnt;i++)if(Sort[i]<1LL*(Sort[i-1])+Sort[i-2])return 1;    return 0;}int main(){    freopen("triangle.in","r",stdin);    freopen("triangle.out","w",stdout);    n=read();m=read();    register int i,x,y,v;    for(i=1;i<=n;i++) a[i]=read();    for(i=1;i