[找规律][逆序数][思维] UVa1620 Lazy Susan

自己看看了半天都找不到规律，倒是感觉和逆序数应该有关系，但是直接按照偶序列有解奇序列无解来算wa，因为按照我原来的理解是，偶序列4个反转一定还是偶序列，奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件，那就是这个是个环，所以他从任意一个地方开始都可以，这就相当于在原来的4个翻转的变换的基础上多了一种变换：把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话，相当于做了i*j次变换，其中i是分界点前一段的个数，j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段，则相乘之后仍然是奇数，等于说这时候是可以从奇序列变成偶序列的；而当n为奇数的时候，i和j必定一奇一偶，这时候相乘必定为偶数，无法变换序列的奇偶性。所以，只有当序列为奇序列且n为奇数的时候才无解，其他情况均有解，因为均可以变换为偶序列。

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;

int a[505],n;
int t[1100];

void change(int x,int p)
{
    while(x<=n)
    {
        t[x]+=p;
        x+= (x&(-x));
    }
    return ;
}

int sum(int k)
{
    int ans=0;
    while(k>0)
    {
        ans+=t[k];
        k-=(k&(-k));
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(t,0,sizeof(t));
        int ans=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=n;i>=1;i--)
        {
            change(a[i],1);
            ans+=sum(a[i]-1);
        }
        if((ans&1)&&(n&1))
        {
            cout<<"impossible\n";
        }
        else
            cout<<"possible\n";
    }
    return 0;
}