Light OJ: 1114 – Easily Readable

0

Problem Link : http://lightoj.com:81/volume/problem/1114


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<":"<<endl
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

map<string,int>mp;
char s1[200],s2[100005];

int main()
{


//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;

    sf(t);
    TEST_CASE(t)
    {
        int n;
        sf(n);
        getchar();
        loop(i,n)
        {
            sc("%s",s1);
            int l=strlen(s1);
            string str(s1,s1+l);
            if(SZ(str)>3)
                sort(str.begin()+1,str.end()-1);
            mp[str]++;
        }

        sf(n);

        getchar();

        PRINT_CASE;

        for(int i=0; i<n; i++)
        {
            ll ans=1;
            gets(s2);
            int l=strlen(s2);
            string str(s2,s2+l);
            stringstream ss;
            ss<<str;
            while(ss>>str)
            {
                if(SZ(str)>3)
                    sort(str.begin()+1,str.end()-1);
                ans*=mp[str];
            }
            pf("%lld\n",ans);

        }

        mp.clear();
    }

    return 0;
}


Light OJ: 1269 – Consecutive Sum

0

Problem Link : http://lightoj.com:81/volume/problem/1269

Solution Idea:

This solution idea is from Manuel Pineda (https://github.com/pin3da) .


/*

Supose that you have an array p, where p[i] is the "accumulative xor" up to i (i.e a[0] ^ a[1] ^ ... a[i]).

For all possible a[i], we can check all the previous a[j], (j < i) in the array "p" and compute the maximum and minimum value of a[i] ^ a[j].

  p.push_back(0);
  for (int i = 0; i < n; ++i) {
    cin >> t;
    cur ^= t;
    for (int j = 0; j < p.size(); ++j) {
      mmin = min(mmin, p[j] ^ cur);
      mmax = max(mmax, p[j] ^ cur);
    }
    p.push_back(cur);
  }
See the brute force solution for details.

This approach lead us to solve the problem, but is not fast enough.

In order to make the solution faster, we need to introduce a trie.

In this trie, we will to save all the prefixes using them binary representation. Use the standard algorithm for that.

If we look the previous solution, this is the equivalent to insert 'mask' in the array 'p'.

  void add(int mask) {
    int cur = 0;
    for (int i = 31; i >= 0; --i) {
      int next = (mask >> i) & 1;
      if (t[cur][next] == -1) {
        t[cur][next] = nodes;
        nodes++;
      }
      cur = t[cur][next];
    }
  }
Then we need to think about how to search the minimum (and the maximum) value that we could get if we perform the xor operation between a mask and all values in the tree. For this, we can make a kind of tree traversal.

The key idea here is : If I'm checking the ith bit of mask and I need the minimum possible value, I will try to advance in the tree using the edge which is equals to the ith bit of the mask in order to get 0 in the result (because we are looking for mask ^ some_number_in_the_tree).

If there is no such edge, I will advance using the other egde.

These words could be confusing, but the code is simpler.

  int get_min(int mask) {
    int cur = 0, ans = 0;
    for (int i = 31; i >= 0; --i) {
      int next = (mask >> i) & 1;
      if (t[cur][next] != -1) {
        ans <<= 1;
        cur = t[cur][next];
      } else {
        cur = t[cur][next ^ 1];
        ans <<= 1;
        ans++;
      }
    }
    return ans;
  }

*/

#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1LL<<50)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(ll N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct node
{
    bool stop;
    node *next[2];
    node()
    {
        stop=0;
        for(int i=0; i<2; i++)
            next[i]=NULL;
    }

};

ll power[50];

void insert(ll mask, node *cur)
{
    for(int i=31; i>=0; i--)
    {
        int id=check(mask,i);
        if(cur->next[id]==NULL)
            cur->next[id]=new node();
        cur=cur->next[id];
    }
    cur->stop=1;
}

ll query_max(ll mask, node *cur)
{
    ll ret=0;
    for(int i=31;i>=0;i--)
    {
        int id=check(mask,i);
        if(cur->next[id^1])
        {
            ret+=power[i];
            cur=cur->next[id^1];
        }
        else
            cur=cur->next[id];
    }
    return ret;
}

ll query_min(ll mask, node *cur)
{
    ll ret=0;
    for(int i=31;i>=0;i--)
    {
        int id=check(mask,i);
        if(cur->next[id])
        {
            cur=cur->next[id];
        }
        else
        {
            ret+=power[i];
            cur=cur->next[id^1];
        }
    }
    return ret;
}

void del(node *cur)
{
    for(int i=0;i<2;i++)
        if(cur->next[i])
            del(cur->next[i]);
    delete (cur);
}

//inline string to_str(ll n)
//{
//    bitset<32>bit(n);
//    return bit.to_string();
//}


int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

//    int aa;
//    cin>>aa;

//    cout<<to_str(aa)<<endl;


  power[0]=1;
  for(int i=1;i<=33;i++)
        power[i]=power[i-1]*2;


  node *root;
//   *small;

   int t;
   sf(t);
   TEST_CASE(t)
   {
       int n;
       sf(n);

       ll maxi=-infinity;
       ll mini=infinity;

       root=new node();
//       small=new node();

//        insert(to_str(0),root);
//        insert(to_str(0),small);
        insert(0,root);
        ll a;

       ll xx=0;

       for(int i=0;i<n;i++)
       {
            sfl(a);
            xx^=a;
//            string str=to_str(xx);
            maxi=max(maxi,query_max(xx,root));
            mini=min(mini,query_min(xx,root));
            insert(xx,root);
       }

    PRINT_CASE;

    pf("%lld %lld\n",maxi,mini);

    del(root);

   }
    return 0;
}


Light OJ: 1129 – Consistency Checker

0

Problem Link : http://lightoj.com:81/volume/problem/1129


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct trie
{
    int stop;
    trie *next[10];
    trie()
    {
        stop=0;
        for(int i=0;i<10;i++)
            next[i]=NULL;
    }
} *root;

bool insert(string str,trie *cur)
{
    int l=SZ(str);
    bool test=0;
    for(int i=0;i<l;i++)
    {
        int now=str[i]-'0';
        if(cur->next[now]==NULL)
        {
            cur->next[now]=new trie();
        }
        if(cur->stop)
        {
            test=1;
            break;
        }
        cur=cur->next[now];
    }
    cur->stop=1;
    return test;
}

void del(trie *cur)
{
    for(int i=0;i<10;i++)
    {
        if(cur->next[i])
            del(cur->next[i]);
    }
    delete (cur);
}

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    cin>>t;
    TEST_CASE(t)
    {
        root = new (trie);
        int n;
        cin>>n;
        string str;
        vector<string>v;
        for(int i=0;i<n;i++)
        {
            cin>>str;
            v.pb(str);
        }

        sort(all(v));

        bool test=0;

        for(int i=0;i<n;i++)
        {
            test=insert(v[i],root);
            if(test) break;
        }
        PRINT_CASE;

        if(test)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
        del(root);
    }


    return 0;
}

UVa 10278 – Fire Station

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1219

Solution Idea:

In this problem the most challenging part is determine how the input is given.
Here for each test case number of edge in the graph is not fixed. You need to take input till end of file. For this strignstream class is used.

And the algorithmic idea is similar like complete search. Place an additional fire station on every intersection which do not contain any fire station already. and run dijkstra for this graph. every time you place a new fire station on an intersection you have to run a dijkstra taking that node as source and also the existing fire stations by input as source. just print the minimum intersection number which minimize the maximum distance.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int u,cost;
    data(int a,int b)
    {
        u=a,cost=b;
    }
    bool operator < (const data &p) const
    {
        return cost>p.cost;
    }
};


vector<int>graph[600],cost[600];
ll dis[600];
bool vis[600];
set<int>st;
int f,k;

void all_clear(int n)
{
    for(int i=0;i<=550;i++)
    {
        graph[i].clear();
        cost[i].clear();
        dis[i]=(1<<28);
        vis[i]=0;
    }
    st.clear();
}


ll dijkastra(int src)
{
    for(int i=0;i<600;i++) dis[i]=(1<<28);

    priority_queue<data>Q;

    stlloop(st)
    {
        dis[*it]=0;
        Q.push(data(*it,0));
    }
    Q.push(data(src,0));
    dis[src]=0;
    ll ret=0;

    while(!Q.empty())
        {
            data u=Q.top();
            Q.pop();
            for(int i=0;i<SZ(graph[u.u]);i++)
            {
                int v=graph[u.u][i];
                if(u.cost+cost[u.u][i]<dis[v])
                {
                    dis[v]=u.cost+cost[u.u][i];
                    Q.push(data(v,dis[v]));
                }

            }
        }

        for(int i=1;i<=k;i++)
            ret=max(ret,dis[i]);
        return ret;
}


int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    CIN;
    int t;
    cin>>t;
    TEST_CASE(t)
    {
//        vector<int>source;
        cin>>f>>k;

        all_clear(k);
        st.clear();

        for(int i=0;i<f;i++)
        {
            int a;
            cin>>a;
            dis[a]=0;
            st.insert(a);
            vis[a]=1;
        }

            string str;
            getline(cin,str);

        while(1)
        {
            getline(cin,str);
            stringstream ss(str);
            if(str.empty()) break;
            int a,b,c;
            ss>>a>>b>>c;
            graph[a].pb(b);
            graph[b].pb(a);
            cost[a].pb(c);
            cost[b].pb(c);
        }



        int ans=1,maxi=100000000;
        for(int i=1;i<=k;i++)
        {
            if(vis[i]==0)
            {
                ll temp=dijkastra(i);
                if(temp<maxi)
                {
                    maxi=temp;
                    ans=i;
                }
            }
        }

        cout<<ans<<endl;
        if(z!=t)
            cout<<endl;
    }

    return 0;
}


Light OJ: 1070 – Algebraic Problem

0

Problem Link : http://lightoj.com:81/volume/problem/1070

(These solution idea is form : http://blog.csdn.net/u013532224/article/details/46862465
and LightOj forum.)


/*

Solution Idea: 

Meaning of the questions:
You p = a + b, q = ab

Calculating (a ^ n + b ^) mod2 ^ 64

practice:

mod 2 ^ 64 so open unsigned long long, llu on the line, reaches the upper limit will be automatically modulo.

Then the formula is. I was pushing the law found in the formula.

a ^ 2 + b ^ 2 = (a + b) * (a + b) -2 * a * b

a ^ 3 + b ^ 3 = (a ^ 2 + b ^ 2) * (a + b) -a * b (a + b)

a ^ 4 + b ^ 4 = (a ^ 3 + b ^ 3) * (a + b) -a * b (a ^ 2 + b ^ 2)

now --

1.a^n + b^n = (a^(n-1)+b^(n-1))*(a+b) - a*b*(a^(n-2)+b^(n-2))
 
2.  Xn = a^n + b^n

3 . Xn = pXn-1 + qXn-2

    (p q)      (Xn-1)         (pXn-1 + qXn-2)         (Xn  )
4.         x               =                      =
    (1 0)      (Xn-2)         ( Xn-1 +  0  )          (Xn-1)

5 . from this

    (p q)^(n-1)     (X1)     (Xn   )   
                x          =
    (1 0)           (X0)     (Xn-1)

*/


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

/*----------------------Matrix-----------------------*/

// int MOD=
// ll MOD=

struct matrix
{
    ull mat[2][2];
    int row,col;

    matrix()
    {
        memset(mat,0,sizeof mat);
    }
    matrix(int a, int b)
    {
        row=a,col=b;
        memset(mat,0,sizeof mat);
    }

    matrix operator*(const matrix &p) const
    {
        assert(col == p.row);
        matrix temp;
        temp.row = row;
        temp.col = p.col;
        for (int i = 0; i < temp.row; i++)
        {
            for (int j = 0; j < temp.col; j++)
            {
                ll sum = 0;
                for (int k = 0; k <col;  k++)
                {
                    sum += ((mat[i][k]) * (p.mat[k][j]));
//                    sum%=MOD;
                }
                temp.mat[i][j] = sum;
            }
        }
        return temp;
    }
    matrix operator+ (const matrix &p) const
    {
        assert(row==p.row && col==p.col);
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<temp.row;i++)
        {
            for(int j=0;j<temp.col;j++)
                temp.mat[i][j]=((mat[i][j])+(p.mat[i][j]));
        }
        return temp;
    }

    matrix identity()
    {
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<row;i++)
            temp.mat[i][i]=1;
        return temp;
    }

    matrix pow(ll pow)
    {
        matrix temp=(*this);
        matrix ret=(*this).identity();
        while(pow)
        {
            if(pow % 2==1)
                ret=ret*temp;
            temp=temp*temp;
            pow/=2;
        }
        return ret;
    }

    void show()
    {
        printf("-----------------------------\n");
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
                printf("%llu ",mat[i][j]);
            printf("\n");
        }
        printf("-----------------------------\n");
    }

};

/*--------------------------Matrix End---------------------*/


int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll p,q,n;
        sfffl(p,q,n);
        matrix base(2,2);
        base.mat[0][0]=p;
        base.mat[0][1]=-q;
        base.mat[1][0]=1;

        matrix temp(2,1);
        temp.mat[0][0]=p;
        temp.mat[1][0]=2;

//        base.show();

        base=base.pow(n-1);
//        base.show();
//        temp.show();
        base=base*temp;
//        ull ans=(base.mat[0][0]*temp.mat[0][0])-(base.mat[0][1]*temp.mat[1][0]);

//        base.show();

        ull ans=base.mat[0][0];
        
        if(n==0) ans=2;
        
        PRINT_CASE;
        printf("%llu\n",ans);

    }

    return 0;
}


Light OJ: 1132 – Summing up Powers

0

Problem Link : http://lightoj.com:81/volume/problem/1132

Soluton Idea:
————–

f(x)=1^k+2^k+3^k+……….+x^k
f(1)=1
f(x+1)=f(x)+(x+1)^k

from Binomial Co efficient we know –
(x+1)^n= nC0 x^n + nC1 x^n-1 + nC2 x^n-2+…………..+ nCn-1 x^1 + nCn x^0

Now make a matrix with co efficient of x so that we can find f(x+1) from f(x).

details: http://lbv-pc.blogspot.com/2012/05/summing-up-powers.html



#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
//#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/



/*----------------------Matrix-----------------------*/

// int MOD=
// ll MOD= (1LL)<<32;

struct matrix
{
    unsigned int mat[52][52];
    int row,col;

    matrix()
    {
        memset(mat,0,sizeof mat);
    }
    matrix(int a, int b)
    {
        row=a,col=b;
        memset(mat,0,sizeof mat);
    }

    matrix operator*(const matrix &p) const
    {
        assert(col == p.row);
        matrix temp;
        temp.row = row;
        temp.col = p.col;
        for (int i = 0; i < temp.row; i++)
        {
            for (int j = 0; j < temp.col; j++)
            {
                ll sum = 0;
                for (int k = 0; k <col;  k++)
                {
                    sum += ((mat[i][k]) * (p.mat[k][j]));
//                    sum%=MOD;
                }
                temp.mat[i][j] = sum;
            }
        }
        return temp;
    }
    matrix operator+ (const matrix &p) const
    {
        assert(row==p.row && col==p.col);
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<temp.row;i++)
        {
            for(int j=0;j<temp.col;j++)
                temp.mat[i][j]=((mat[i][j])+(p.mat[i][j]));;
        }
        return temp;
    }

    matrix identity()
    {
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<row;i++)
            temp.mat[i][i]=1;
        return temp;
    }

    matrix pow(ll pow)
    {
        matrix temp=(*this);
        matrix ret=(*this).identity();
        while(pow)
        {
            if(pow % 2==1)
                ret=ret*temp;
            temp=temp*temp;
            pow/=2;
        }
        return ret;
    }

    void show()
    {
        printf("-----------------------------\n");
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
                printf("%lld ",mat[i][j]);
            printf("\n");
        }
        printf("-----------------------------\n");
    }

};

/*--------------------------Matrix End---------------------*/

unsigned int nCr[55][55];

void compute_nCr()
{
    nCr[0][0]=nCr[1][1]=1;
    for(int i=1;i<52;i++)
    {
        nCr[i][0]=1;
        for(int j=1;j<52;j++)
            nCr[i][j]=nCr[i-1][j]+nCr[i-1][j-1];
    }
}

int main()
{

//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    compute_nCr();

//    int a=5;
//    while(a--)
//    {
//        int a,b;
//        cin>>a>>b;
//        cout<<nCr[a][b]<<endl;
//    }

    TEST_CASE(t)
    {
        ll n,k;
        sffl(n,k);
        matrix base(k+2,k+2);

        base.mat[0][0]=1;

        for(int i=1;i<=k+1;i++)
        {
            base.mat[0][i]=nCr[k][i-1];
            base.mat[1][i]=nCr[k][i-1];
        }
        for(int i=2;i<=k+1;i++)
        {
            for(int j=i;j<=k+1;j++)
                base.mat[i][j]=nCr[k-i+1][j-i];
        }

//        base.show();

        matrix temp(k+2,1);
        for(int i=0;i<=k+1;i++)
            temp.mat[i][0]=1;

        base=base.pow(n-1);
//        base.show();
//        temp.show();
        base=base*temp;
        PRINT_CASE;
        printf("%u\n",base.mat[0][0]);



    }

    return 0;
}


Light OJ: 1131 – Just Two Functions

0

Problem Link : http://lightoj.com:81/volume/problem/1131


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
//#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

/*----------------------Matrix-----------------------*/

// int MOD=
 ll MOD;

struct matrix
{
    ll mat[7][7];
    int row,col;

    matrix()
    {
        memset(mat,0,sizeof mat);
    }
    matrix(int a, int b)
    {
        row=a,col=b;
        memset(mat,0,sizeof mat);
    }

    matrix operator*(const matrix &p) const
    {
        assert(col == p.row);
        matrix temp;
        temp.row = row;
        temp.col = p.col;
        for (int i = 0; i < temp.row; i++)
        {
            for (int j = 0; j < temp.col; j++)
            {
                ll sum = 0;
                for (int k = 0; k <col;  k++)
                {
                    sum += ((mat[i][k]%MOD) * (p.mat[k][j]%MOD))%MOD;
                    sum%=MOD;
                }
                temp.mat[i][j] = sum;
            }
        }
        return temp;
    }
    matrix operator+ (const matrix &p) const
    {
        assert(row==p.row && col==p.col);
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<temp.row;i++)
        {
            for(int j=0;j<temp.col;j++)
                temp.mat[i][j]=((mat[i][j]%MOD)+(p.mat[i][j]%MOD))%MOD;;
        }
        return temp;
    }

    matrix identity()
    {
        matrix temp;
        temp.row=row;
        temp.col=col;
        for(int i=0;i<row;i++)
            temp.mat[i][i]=1;
        return temp;
    }

    matrix pow(ll pow)
    {
        matrix temp=(*this);
        matrix ret=(*this).identity();
        while(pow)
        {
            if(pow % 2==1)
                ret=ret*temp;
            temp=temp*temp;
            pow/=2;
        }
        return ret;
    }

    void show()
    {
        printf("-----------------------------\n");
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
                printf("%lld ",mat[i][j]);
            printf("\n");
        }
        printf("-----------------------------\n");
    }

};

/*--------------------------Matrix End---------------------*/

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int a1,b1,c1,a2,b2,c2,f0,f1,f2,g0,g1,g2;
        sfff(a1,b1,c1);
        sfff(a2,b2,c2);
        sfff(f0,f1,f2);
        sfff(g0,g1,g2);
        sfl(MOD);

        matrix base(6,6);
        base.mat[0][0]=a1;
        base.mat[0][1]=b1;
        base.mat[0][5]=c1;
        base.mat[1][0]=1;
        base.mat[2][1]=1;
        base.mat[3][2]=c2;
        base.mat[3][3]=a2;
        base.mat[3][4]=b2;
        base.mat[4][3]=1;
        base.mat[5][4]=1;

        matrix temp(6,1);
        temp.mat[0][0]=f2%MOD;
        temp.mat[1][0]=f1%MOD;
        temp.mat[2][0]=f0%MOD;
        temp.mat[3][0]=g2%MOD;
        temp.mat[4][0]=g1%MOD;
        temp.mat[5][0]=g0%MOD;

        int q;
        sf(q);
        PRINT_CASE;
        while(q--)
        {
            int n;
            sf(n);
            ll ans1,ans2;
            if(n<=2)
            {
                ans1=temp.mat[2-n][0];
                ans2=temp.mat[5-n][0];
            }
            else
            {
                matrix power=base.pow(n-2);
                power = power*temp;
                ans1=power.mat[0][0];
                ans2=power.mat[3][0];
            }
            printf("%lld %lld\n",ans1,ans2);
        }


    }

    return 0;
}