1001：Inversion

模版题，求逆序数对。有多少逆序数对，就可以剪掉多少。

1003：Least common multiple

对于每一个子集，lcm为2的a的最大值次方*3的b的最大值次方。

所以我们只需要求出以某个b为b的最大值的时候，a的最大值的分布情况即可。

我们先把b从小到大排序。

对于某一个b，我门只需要求出之前出现过的a比当前a小的数量为x；

那么就可知对于这些a的子集，为2^x个，并且，每个子集a的最大值都为当前a。

我么还需要求出对于大于当前a的a有多少个比a小的数，我们可以用线段树逐步维护。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;
#define LL long long
#define lcm(a,b) (a*b/gcd(a,b))
#define maxn 110000
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
struct list
{
    int a,b;
    friend bool operator <(const list &a,const list &b)
    {
        return a.b<b.b;
    }
}p[maxn];
int cmp(list a,list b)
{
    return a.a<b.a;
}
int ed[maxn];
LL num[maxn<<2];
LL sum[maxn<<2];
LL lazy[maxn<<2];
void push_down(int rt)
{
    if(lazy[rt]!=1)
    {
        sum[rt<<1]*=lazy[rt];
        sum[rt<<1|1]*=lazy[rt];
        sum[rt<<1]%=mod;
        sum[rt<<1|1]%=mod;
        lazy[rt<<1]*=lazy[rt];
        lazy[rt<<1|1]*=lazy[rt];
        lazy[rt<<1]%=mod;
        lazy[rt<<1|1]%=mod;
        lazy[rt]=1;
    }
}
void push_up(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    num[rt]=num[rt<<1]+num[rt<<1|1];
    sum[rt]%=mod;
}
void creat(int l,int r,int rt)
{
    num[rt]=sum[rt]=0;
    lazy[rt]=1;
    if(l!=r)
    {
        creat(lson);
        creat(rson);
        return;
    }
}
void insert(int x,int l,int r,int rt)
{
    if(x<l||x>r)return;
    if(l==r&&l==x)
    {
        num[rt]++;
        sum[rt]=M.q_mod(2,ed[x],mod);
        sum[rt]=(sum[rt]*lazy[rt])%mod;
        return;
    }
    push_down(rt);
    insert(x,lson);
    insert(x,rson);
    push_up(rt);
}
void updata(int ll,int rr,int l,int r,int rt)
{
    if(ll>rr)return ;
    if(ll>r||rr<l)return;
    if(ll<=l&&rr>=r)
    {
        lazy[rt]*=2;
        sum[rt]=sum[rt]*2%mod;
        return;
    }
    push_down(rt);
    updata(ll,rr,lson);
    updata(ll,rr,rson);
    push_up(rt);
}
LL query(int ll,int rr,int leap,int l,int r,int rt)
{
    if(ll>rr)return 0;
    if(ll>r||rr<l)return 0;
    if(ll<=l&&rr>=r)
    {
        if(leap==0)return num[rt];
        else return sum[rt];
    }
    push_down(rt);
    return query(ll,rr,leap,lson)+query(ll,rr,leap,rson);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].a,&p[i].b);
        }
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            ed[i]=p[i].a;
            p[i].a=i;
        }
        creat(1,n,1);
        sort(p+1,p+n+1);
        LL sum=0;
        for(int i=1;i<=n;i++)
        {
            int k=p[i].a;
            LL x=query(1,k-1,0,1,n,1);
            LL y=query(k+1,n,1,1,n,1);
            LL now=M.q_mod(3,p[i].b,mod);
            LL ps=((M.q_mod(2,ed[k],mod))*(M.q_mod(2,x,mod)))%mod;
            sum+=now*((ps+y)%mod)%mod;
            insert(k,1,n,1);
            updata(k+1,n,1,n,1);
            sum=sum%mod;
        }
        cout<<sum<<endl;
    }
    return 0;
}

1005：Parenthese sequence

我的做法好像不是正经做法。。。sad

首先对于每一个）进行匹配（，如果匹配不到（，就匹配最前面的？，如果无法匹配，那就肯定无解。

一遍匹配之后，还剩下（还有？。

把每一个剩下的（匹配最后面的？；如果匹配不到？，肯定无解。

假如现在剩下x个？；

如果x是奇数，肯定无解。

如果x为0，肯定唯一解。

如果x>2，肯定多解。

如果x=2，那就把第一个？置为），第二个？置为（，如果可信，那就多解，否则，唯一解。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
#define gcd(a,b) (b==0?a:gcd(b,a%b))
#define lcm(a,b) (a*b/gcd(a,b))
int pre[1100000];
int next[1100000];
char str[1100000];
stack<int>st;
stack<int>we;
int biao[1100000];
int fbiao[1100000];
int main()
{
    while(~scanf("%s",str))
    {
        while(!st.empty())st.pop();
        while(!we.empty())we.pop();
        memset(pre,-1,sizeof(pre));
        memset(next,-1,sizeof(next));
        int len=strlen(str);
        int last=-1;
        int leap=0;
        int sts=-1;
        for(int i=0;i<len;i++)
        {
            if(str[i]=='(')
            {
                st.push(i);
            }
            else if(str[i]==')')
            {
                if(st.empty())
                {
                    leap=1;
                    if(sts==-1)
                    {
                        leap=-1;
                        break;
                    }
                    else
                    {
                        str[sts]='(';
                        sts=next[sts];
                        if(sts==-1)
                        {
                            pre[sts]=-1;
                            sts=last=-1;
                        }
                        else pre[sts]=-1;
                    }
                }
                else
                {
                    int x=st.top();
                    st.pop();
                }
            }
            else if(str[i]=='?')
            {
                pre[i]=last;
                if(sts==-1)sts=i;
                else next[last]=i;
                last=i;
               // cout<<sts<<endl;
            }
        }
        if(leap==-1)
        {
            cout<<"None"<<endl;
            continue;
        }
        while(!st.empty())
        {
            if(last==-1)
            {
                break;
            }
            int x=st.top();
            if(x<last)
            {
                st.pop();
                str[last]=')';
                last=pre[last];
            }
            else break;
        }
        int ss=0;
        while(last!=-1)
        {
            last=pre[last];
            ss++;
        }
       // cout<<ss<<endl;
        if(leap==-1||!st.empty()||ss%2)
        {
            cout<<"None"<<endl;
            continue;
        }
        if(ss>2)
        {
            cout<<"Many"<<endl;
            continue;
        }
        if(ss==0)
        {
            cout<<"Unique"<<endl;
            continue;
        }
        while(!st.empty())st.pop();
        int lp=0;
        leap=1;
       // cout<<str<<endl;
        for(int i=0;i<len;i++)
        {
            if(str[i]=='?')
            {
                if(lp==0)
                {
                    str[i]=')';
                    lp++;
                }
                else str[i]='(';
            }
        }
     //   cout<<str<<endl;
        int i;
        for(i=0;i<len;i++)
        {
            if(str[i]=='(')st.push(i);
            else if(str[i]==')')
            {
                if(st.empty())break;
                else st.pop();
            }
        }
        if(i<len)cout<<"Unique"<<endl;
        else cout<<"Many"<<endl;
    }
    return 0;
}

因为结果是一些数的异或和。

我们就可以枚举每一位为1时，是由哪些数异或得来的。

对于当前位，如果A,B异或结果为1，那么A，B这两个数的当前位一个为1，一个为0，共有两种情况。

已知A+B=n。

那么对于当前位之前的数的和可以求出x种情况，对于当前位之后的数的和可以求出有y种情况。

那么总过有x*y*2种情况。

又因为A,B都是非0的，所以还需要减去0的情况。

又因为是大数。。。所以要用java，大数用C++太费劲了。。

import java.util.Scanner;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger n,m,sum,zero,one,two,x,k,y,ta,tb,z;
        BigInteger bit[] = new BigInteger[3300];
        bit[0] = BigInteger.valueOf(1);
        int i;
        for(i = 1;i <= 3000;i ++)
            bit[i] = bit[i-1].multiply(BigInteger.valueOf(2));
        zero = BigInteger.valueOf(0);
        one = BigInteger.valueOf(1);
        two = BigInteger.valueOf(2);
        while(cin.hasNext())
        {
            n = cin.nextBigInteger();
            m = n;
            sum = BigInteger.valueOf(0);
            for(i = 1;;i ++)
            {
                n = m.subtract(bit[i-1]);
                if(n.compareTo(zero) == -1)
                    break;
                x=n.divide(bit[i]).add(one);
                k=n.mod(bit[i]);
                if(bit[i-1].subtract(one).compareTo(k) == -1)
                    ta = bit[i-1].subtract(one);
                else 
                    ta = k;
                if(zero.compareTo(k.subtract(bit[i-1]).add(one)) == 1)
                    tb = zero;
                else 
                    tb = k.subtract(bit[i-1]).add(one);
                y=ta.subtract(tb).add(one);
                sum = sum.add(x.multiply(y).multiply(two).multiply(bit[i-1]));
                z = m.divide(bit[i]);
                k = m.divide(bit[i-1]);
                z = z.multiply(two);
                if(k.compareTo(z) != 0)
                {
                    sum = sum.subtract(bit[i-1].multiply(two));
                }
            }
            System.out.println(sum);
        }

    }
}

瞎搞题，把所有的0都去掉，然后就可以了。。。

理论时间复杂度为800*800*800*（2/3)*(2/3)

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
#define gcd(a,b) (b==0?a:gcd(b,a%b))
#define lcm(a,b) (a*b/gcd(a,b))
//O（n）求素数，1-n的欧拉数
#define N 100010
//A^x = A^(x % Phi(C) + Phi(C)) (mod C)
int a[880][880];
int b[880][880];
int aa[880][880];
int bb[880][880];
int c[880][880];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(aa,0,sizeof(aa));
        memset(bb,0,sizeof(bb));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
                a[i][j]%=3;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&b[i][j]);
                b[i][j]%=3;
            }
        }
        for(int i=1;i<=n;i++)
        {
            int x=-1;
            for(int j=n;j>=0;j--)
            {
                aa[i][j]=x;
                if(a[i][j])x=j;
            }
        }
        for(int i=1;i<=n;i++)
        {
            int x=-1;
            for(int j=n;j>=0;j--)
            {
                bb[i][j]=x;
                if(b[i][j])x=j;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=aa[i][0];j!=-1;j=aa[i][j])
            {
                for(int k=bb[j][0];k!=-1;k=bb[j][k])
                    c[i][k]+=a[i][j]*b[j][k];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                printf("%d",c[i][j]%3);
                if(j!=n)printf(" ");
                else printf("\n");
            }
        }
    }
    return 0;
}