[JAVA]HDU 4919 Exclusive or

题意很简单, 就是给个n, 算下面这个式子的值.

$sumlimits_{i=1}^{n-1} i otimes (n-i)$

重点是n的范围:2≤n<10⁵⁰⁰

比赛的时候 OEIS一下得到了一个公式:

$a_0=a_1=a_2=0$;

n为偶数 : $2 imes a_{frac{n}{2}}+2 imes a_{frac{n}{2}-1}+4 imes (frac{n}{2}-1) $

n为奇数 : $4 imes a_{frac{n-1}{2}}+6 imesfrac{n-1}{2}$

然后勇敢的打了一发暴力...想也知道肯定TLE...

之后 学到了一种机智的按位算的方法

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
    static BigInteger yi=BigInteger.ONE;
    static BigInteger er=BigInteger.valueOf(2);
    static BigInteger li=BigInteger.ZERO;
    public static void main(String[] args)
    {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        BigInteger []bit=new BigInteger[2005];
        bit[0]=yi;
        for(int i=1; i<=2000; i++)
            bit[i]=bit[i-1].multiply(er);
        while(in.hasNext())
        {
            BigInteger n=new BigInteger(in.next());
            int []wei=new int[2005];
            int d=0;
            BigInteger []a=new BigInteger[2005];
            BigInteger []b=new BigInteger[2005];
            BigInteger tmp=n;
            while(tmp.compareTo(li)!=0)
            {
                if(tmp.mod(er).equals(li))
                    wei[d++]=0;
                else 
                    wei[d++]=1;
                tmp=tmp.divide(er);
            }
            BigInteger sum=li, ji=yi;
            for(int i=0; i<d; i++)
            {
                if(wei[i]>0)
                    sum=sum.add(ji);
                ji=ji.multiply(er);
                a[i+1]=sum;
            }
            sum=li;
            for(int i=d; i>=0; i--)
            {
                sum=sum.multiply(er).add(BigInteger.valueOf(wei[i]));
                b[i+1]=sum;
            }
            a[0]=li;
            BigInteger ans=li;
            for(int i=0; i<d; i++)
                if(wei[i]==0)
                {
                    BigInteger an=(bit[i].subtract(a[i]).subtract(yi)).multiply(b[i+2]).multiply(bit[i]);
                    ans=ans.add(an).add(an);
                }
                else 
                {
                    BigInteger an=((a[i].add(yi)).multiply(b[i+2].add(yi)).subtract(yi)).multiply(bit[i]);
                    ans=ans.add(an).add(an);
                }
            out.println(ans);
        }
        out.close();
    }
}
class InputReader
{
    BufferedReader buf;
    StringTokenizer tok;
    InputReader()
    {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext()
    {
        while(tok == null || !tok.hasMoreElements()) 
        {
            try
            {
                tok = new StringTokenizer(buf.readLine());
            } 
            catch(Exception e) 
            {
                return false;
            }
        }
        return true;
    }
    String next()
    {
        if(hasNext()) 
            return tok.nextToken();
        return null;
    }
    int nextInt()
    {
        return Integer.parseInt(next());
    }
    long nextLong()
    {
        return Long.parseLong(next());
    }
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger()
    {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal()
    {
        return new BigDecimal(next());
    }
}

再之后 学习了一下map的记忆化搜索

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
    static BigInteger yi=BigInteger.ONE;
    static BigInteger er=BigInteger.valueOf(2);
    static BigInteger li=BigInteger.ZERO;
    static BigInteger sa=BigInteger.valueOf(3);
    static BigInteger si=BigInteger.valueOf(4);
    static BigInteger liu=BigInteger.valueOf(6);
    static HashMap<BigInteger, BigInteger> a=new HashMap<BigInteger, BigInteger>();
    public static BigInteger dfs(BigInteger n)
    {
        if(a.containsKey(n))
            return a.get(n);
        BigInteger m;
        if(n.mod(er).equals(li))
        {
            BigInteger aa=n.divide(er);
            BigInteger bb=dfs(aa).multiply(er);
            BigInteger cc=dfs(aa.subtract(yi)).multiply(er);
            m=(aa.subtract(yi)).multiply(si).add(bb).add(cc);
        }
        else
        {
            BigInteger aa=(n.subtract(yi)).divide(er);
            m=dfs(aa).multiply(si).add(aa.multiply(liu));
        }
        a.put(n, m);
        return m;
    }
    public static void main(String[] args)
    {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        a.put(li, li);
        a.put(yi, li);
        a.put(er, li);
        while(in.hasNext())
        {
            BigInteger n=new BigInteger(in.next());
            out.println(dfs(n));
        }
        out.close();
    }
}
class InputReader
{
    BufferedReader buf;
    StringTokenizer tok;
    InputReader()
    {
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext()
    {
        while(tok == null || !tok.hasMoreElements()) 
        {
            try
            {
                tok = new StringTokenizer(buf.readLine());
            } 
            catch(Exception e) 
            {
                return false;
            }
        }
        return true;
    }
    String next()
    {
        if(hasNext()) 
            return tok.nextToken();
        return null;
    }
    int nextInt()
    {
        return Integer.parseInt(next());
    }
    long nextLong()
    {
        return Long.parseLong(next());
    }
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger()
    {
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal()
    {
        return new BigDecimal(next());
    }
}