b_fast.cpp

gistfile1.txt

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

class Mat
{

private:

    ull n;
    vector<int> t;
    
public:

    Mat(ull n);
    Mat(const Mat& mat);

    void setIdent();

    int get(ull x, ull y)const;
    void set(ull x, ull y, int val);
    Mat operator+(const Mat& mat)const;
    Mat operator-(const Mat& mat)const;
    Mat operator*(const Mat& mat)const;
    Mat pow(ull n)const;

    ull getSize()const;

    string toString()const;
    string toStringSpaceless()const;
        
};

double maxIndex(ull n);
bool solve(Mat& res, ull target);


int main()
{
    int nn;
    cin >> nn;
    for(int kk=1; kk<=nn; kk++)
    {

        cout << "Case #" << kk << ": ";
        
        ull B, M;
        cin >> B >> M;

        Mat res(B);
        if(!solve(res, M))
        {
            cout << "IMPOSSIBLE" << endl;
        }
        else
        {
            cout << "POSSIBLE" << endl;
            cout << res.toStringSpaceless() << endl;
        }

    }
}

Mat::Mat(ull n)
{
    this->n = n;
    t = vector<int>(n*n);
}

Mat::Mat(const Mat& mat)
{
    n = mat.n;
    t = mat.t;
}

void Mat::setIdent()
{
    for(ull i=0; i<t.size(); i++)
    {
        t[i] = 0;
    }
    for(int i=0; i<n; i++)
    {
        set(i, i, 1);
    }
}

int Mat::get(ull x, ull y)const
{
    return t[y*n + x];
}

void Mat::set(ull x, ull y, int val)
{
    t[y*n + x] = val;
}

Mat Mat::operator+(const Mat& mat)const
{
    Mat res(*this);
    for(ull i=0; i<res.t.size(); i++)
    {
        res.t[i] += mat.t[i];
    }
    return res;
}

Mat Mat::operator-(const Mat& mat)const
{
    Mat res(*this);
    for(ull i=0; i<res.t.size(); i++)
    {
        res.t[i] -= mat.t[i];
    }
    return res;
}

Mat Mat::operator*(const Mat& mat)const
{
    Mat res(*this);
    for(ull y=0; y<n; y++)
    for(ull x=0; x<n; x++)
    {
        int val = 0;
        for(ull i=0; i<n; i++)
        {
            val += this->get(i, y) * mat.get(x, i);
        }
        res.t[y*n + x] = val;
    }
    return res;
}

Mat Mat::pow(ull n)const
{
    Mat res(this->n); res.setIdent();
    for(int i=0; i<n; i++)
    {
        res = res * (*this);
    }
    return res;
}

ull Mat::getSize()const
{
    return n;
}

string Mat::toString()const
{
    stringstream ss;
    for(ull y=0; y<n; y++)
    {
        for(ull x=0; x<n; x++)
        {
            ss << t[y*n + x];
            if(x != n-1) ss << " ";
        }
        if(y != n-1) ss << endl;
    }
    return ss.str();
}

string Mat::toStringSpaceless()const
{
    stringstream ss;
    for(ull y=0; y<n; y++)
    {
        for(ull x=0; x<n; x++)
        {
            ss << t[y*n + x];
        }
        if(y != n-1) ss << endl;
    }
    return ss.str();
}

double maxIndex(ull n)
{
    return pow(2, n-2);
}

bool solve(Mat& res, ull target)
{

    ull n = res.getSize();

    if(target > maxIndex(n)) return false;

    vector<unsigned char> vo;
    ull t = target-1;
    while(t > 0)
    {
        ull x = t%2;
        vo.push_back(x);
        t /= 2;
    }

    res.set(n-1, 0, 1);
    
    for(int i=0; i<vo.size(); i++)
    {
        res.set(n-i-2, 0, vo[i]);
    }

    for(int i=0; i<vo.size(); i++)
    {
        for(int j=0; j<i+1; j++)
        {
            res.set(n-j-1, n-i-2, 1);
        }
    }

    return true;
    
}