count the tetris(置换群).cpp

杭电acm解题报告2001---2099.

/**** **** **** **** **** ****
*    Function Name :    BigNumber
*    Description :        BigNumber's HPC
*    Author :            HuangWei
*    Last Edited :        07.8.25
**** **** **** **** **** ****/
#include <iostream>
#include <string>
#include <sstream>
#include <memory>
#include <algorithm>

#define BASE    1000    // 基数
#define DIG        600    // 存储
using namespace std;

class BigNumber
{
private:
    int data[DIG];    // 数据区
    int len;        // 记录长度
public:
    BigNumber()     {len=1;memset(data,0,sizeof(data));data[0]=1;}
    BigNumber(int);    // 输入默认十进制
    BigNumber(char*);
    BigNumber(const BigNumber &);
    // 类型转换
    BigNumber & Num_BNum(int);
    BigNumber & Str_BNum(char*);
    int Int();
    string Str();
    void cprint();
    // HPC
    BigNumber & Add(const BigNumber &);
    BigNumber & Sub(const BigNumber &);
    BigNumber & Mul(const BigNumber &);
    BigNumber & Div(int);
    BigNumber & Mod(int);
    BigNumber & operator=(const BigNumber &);
    int Bigger(const BigNumber &) const;

    BigNumber operator + (const BigNumber &);
    BigNumber operator - (const BigNumber &);
    BigNumber operator * (const BigNumber &);
    BigNumber operator / (int);
    BigNumber operator % (int);
    BigNumber operator ^ (int);

    BigNumber & operator += (const BigNumber &);
    BigNumber & operator -= (const BigNumber &);
    BigNumber & operator *= (const BigNumber &);
    BigNumber & operator /= (int);
    BigNumber & operator %= (int);
};

BigNumber & BigNumber::Num_BNum(int b)
{
    len=1;     memset(data,0,sizeof(data));
    data[0] = 1;
    if(b < 0) {
        b = -b;
        data[0] = -1;
    }
    while(b > 0) {
        data[ len++ ] = b % BASE;
        b /= BASE;
    }
    return *this;
}

BigNumber & BigNumber::Str_BNum(char* sb)
{
    int t=0, d=1, b=0, slen=strlen(sb), i;
    len=1;     memset(data,0,sizeof(data));
    data[0] = 1;
    if(sb[0] == '-')     data[0] = -1, b=1;
    for(i=slen-1; i>=b ;i--) {
        while(t >= BASE || d > BASE) {
            data[ len++ ] = t % BASE;
            t /= BASE;
            d = 10;
        }
        t += (sb[i]-'0') * d;
        d *= 10;
    }
    while(t > 0) {
        data[ len++ ] = t % BASE;
        t /= BASE;
    }
    return *this;
}

int BigNumber::Int() 
{
    istringstream sin;
    int v;
    sin.str( this->Str() );
    sin >> v;
    return v;
}

string BigNumber::Str()
{
    int i,base_len=0;
    ostringstream sout;
    if(len == 1) {
        sout << '0';
        //sout << endl;
        return sout.str();
    }
    if(data[0] < 0)     sout << "-";
    sout << data[len-1];
    i = BASE;
    while(i > 1) {
        base_len++;
        i /= 10;
    }
    for(i=len-2; i>0 ;i--) {
        sout.width(base_len);
        sout.fill('0');
        sout << data[i];
    }
    //sout << endl;
    return sout.str();
}

BigNumber::BigNumber(int b)
{this->Num_BNum(b);}

BigNumber::BigNumber(char* sb)
{this->Str_BNum(sb);}
// -1 a<b, 0 a==b, 1 a>b
BigNumber::BigNumber(const BigNumber & b)
{len = b.len;     memcpy(data,b.data,sizeof(data));}

int BigNumber::Bigger(const BigNumber & b) const
{
    int i,flag;
    if(data[0] ==1 && b.data[0] ==1)        flag = 1;
    else if(data[0] ==1 && b.data[0] ==-1)    return 1;
    else if(data[0] ==-1 && b.data[0] ==1)    return -1;
    else    flag = -1;

    if(len > b.len)     return flag;
    else if(len == b.len) {
        for(i=len-1; i>0 ;i--)
            if(data[i] > b.data[i])     return flag;
    }
    if(i == 0)     return 0;
    return -flag;
}

BigNumber & BigNumber::Add(const BigNumber & b)
{
    int i;
    if(data[0] * b.data[0] != 1) {
        data[0] = -data[0];
        Sub(b);
        data[0] = -data[0];
        return *this;
    }
    len= len > b.len ? len : b.len;
    for(i=1; i<len ;i++) {
        data[i] += b.data[i];
        if(data[i] >= BASE) {
            data[i+1]++;
            data[i] -= BASE;
        }
    }
    if(data[i] > 0)     len = i+1;
    return *this;
}

BigNumber & BigNumber::Sub(const BigNumber & b)
{
    int i;
    if(data[0] * b.data[0] != 1) {
        data[0] = -data[0];
        Add(b);
        data[0] = -data[0];
        return *this;
    }
    len= len > b.len ? len : b.len;
    for(i=1; i<len ;i++) {
        data[i] -= b.data[i];
        if(data[i] < 0) {
            data[i+1]--;
            data[i] += BASE;
        }
    }
    if(data[len] < 0) {
        for(i=0; i<=len ;i++)
            data[i] = -data[i];
        for(i=1; i<len ;i++)
            if(data[i] < 0) {
                data[i+1]--;
                data[i] += BASE;
            }
    }
    while(data[len-1] == 0)     len--;
    return *this;
}

BigNumber & BigNumber::Mul(const BigNumber & b)
{
    BigNumber bt;
    int i,j,up;
    int temp,temp1;

    bt.data[0] = data[0] * b.data[0];
    for(i=1; i<len ;i++) {
        up = 0;
        for(j=1; j<b.len ;j++) {
            temp = data[i] * b.data[j] + bt.data[i+j-1] + up;
            if(temp >= BASE) {
                temp1 = temp % BASE;
                up = temp / BASE;
                bt.data[i+j-1] = temp1;
            }
            else {
                up = 0;
                bt.data[i+j-1] = temp;
            }
        }
        if(up != 0)     bt.data[i+j-1] = up;
    }
    bt.len = i+j;
    while(bt.data[bt.len-1] == 0) bt.len--;
    *this=bt;
    return *this;
}

BigNumber & BigNumber::Div(int b)
{
    BigNumber bt;
    int i,down = 0;

    if(b < 0)     bt.data[0] = -data[0] , b = -b;
    else          bt.data[0] = data[0];
    for(i=len-1; i>=1 ;i--) {
        bt.data[i] = (data[i] + down * BASE) / b;
        down = data[i] + down * BASE - bt.data[i] * b;
    }
    bt.len = len;
    while(bt.data[bt.len-1] == 0)     bt.len--;
    *this=bt;
    return *this;
}

BigNumber & BigNumber::Mod(int b)
{
    int temp = 0, up = 0, i;
    for(i=len-1; i>=1 ;i--) {
        temp = data[i];
        temp += up * BASE;
        up = temp % b;
    }
    if(data[0] < 0)     up = -up;
    *this = up;
    return *this;
}

BigNumber BigNumber::operator ^ (int b)
{
    BigNumber bt = *this;
    BigNumber bt2 = 1;
    int i,j;
    if(b == 0) {
        return bt2;
    }
    else {
        while(b > 1) {
            if(b%2) {
                bt2 *= bt;
            }
            bt *= bt;
            b /= 2;
        }
    }
    return bt*bt2;
}

void BigNumber::cprint()
{
    int i,base_len=0;
    if(len == 1) {
        printf("0\n");
        return ;
    }
    if(data[0] < 0)    printf("-");
    printf("%d", data[len-1]);
    i = BASE;
    while(i > 1) {
        base_len++;
        i /= 10;
    }
    for(i=len-2; i>0 ;i--) {
        printf("%0*d", base_len ,data[i]);
    }
    printf("\n");
}

BigNumber & BigNumber::operator = (const BigNumber & b)
{len = b.len;     memcpy(data,b.data,sizeof(data));     return *this;}

BigNumber BigNumber::operator + (const BigNumber & b)
{BigNumber bt=*this;     return bt.Add(b);}

BigNumber BigNumber::operator - (const BigNumber & b)
{BigNumber bt=*this;     return bt.Sub(b);}

BigNumber BigNumber::operator * (const BigNumber & b)
{BigNumber bt=*this;     return bt.Mul(b);}

BigNumber BigNumber::operator / (int b)
{BigNumber bt=*this;     return bt.Div(b);}

BigNumber BigNumber::operator % (int b)
{BigNumber bt=*this;     return bt.Mod(b);}

BigNumber & BigNumber::operator += (const BigNumber & b)
{return this->Add(b);}

BigNumber & BigNumber::operator -= (const BigNumber & b)
{return this->Sub(b);}

BigNumber & BigNumber::operator *= (const BigNumber & b)
{return this->Mul(b);}

BigNumber & BigNumber::operator /= (int b)
{return this->Div(b);}

BigNumber & BigNumber::operator %= (int b)
{return this->Mod(b);}

BigNumber ans[32][32];

BigNumber f(int n,int c)
{
    if(c == 1 || n == 1) {
        return BigNumber(c);
    }
    BigNumber base = c;
    return base ^ n;
}

int main()
{
    int n,c;
    for(n=1;n<=30;n++) {
        for(c=1;c<=30;c++) {
            ans[n][c] = 0;
            ans[n][c] += f(n*n,c) + f((n*n+3)/4,c)*2 + f((n*n+1)/2,c);
            if(n%2) {
                ans[n][c] += f((n*n+n)/2,c)*4;
            }
            else {
                ans[n][c] += f(n*n/2,c)*2 + f((n*n+n)/2,c)*2;
            }
            ans[n][c] /= 8;
        }
    }
    while(scanf("%d %d",&n,&c)==2) {
        ans[n][c].cprint();
    }
}