UVa 10679 – I Love Strings!!

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

Solution Idea: Build Suffix Array then binary search on the sorted sequence.


#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 LINE_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));}
/*------------------------------------------------*/

#define mx 100005

int suffix_array[mx],position[mx];

struct data
{
    pii rank;
    int pos;
};

bool cmp(data a, data b)
{
    return a.rank<b.rank;
}

char str[mx],query[mx];

int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        scanf("%s",str);

        int n=strlen(str);

        for(int i=0;i<n;i++) position[i]=str[i];

        for(int k=1;k<n;k*=2)
        {
            vector<data>v(n);
            for(int i=0;i<n;i++)
            {
                int a=position[i];
                int b;
                if(i+k>=n)
                    b=-1;
                else
                    b=position[i+k];
                v[i].rank=pii(a,b);
                v[i].pos=i;
            }

            sort(all(v),cmp);

            position[v[0].pos]=0;
            suffix_array[0]=v[0].pos;
            for(int i=1;i<n;i++)
            {
                suffix_array[i]=v[i].pos;
                if(v[i].rank==v[i-1].rank)
                    position[v[i].pos]=position[v[i-1].pos];
                else
                    position[v[i].pos]=i;
            }
        }

        int q;
        sf(q);
        while(q--)
        {
            scanf("%s",query);
            int l=strlen(query);
            int lo=0,hi=n-1;
            bool ans=0;
            while(lo<=hi)
            {
                int mid=(lo+hi)/2;
                int x=strncmp(str+suffix_array[mid],query,l);
                if(x==0)
                {
                    ans=1;
                    break;
                }
                else if(x>0)
                    hi=mid-1;
                else
                    lo=mid+1;
            }
            if(ans)
                pf("y\n");
            else
                pf("n\n");
        }
    }

    return 0;
}


Advertisements

UVa 1314 – Hidden Password

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

Solution Idea: Concatenate the input string with itself and find the suffix array. Answer will be the smallest string in suffix array which lie between index 0 to n-1 and which index is smaller.


#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 LINE_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));}
/*------------------------------------------------*/


char ara[100005];

struct data
{
    pii rank;
    int pos;
};

bool cmp(data a, data b)
{
    return a.rank<b.rank;
}

int suffix_ara[200005];

int position[200005];

int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n;
        sf(n);
        getchar();
        gets(ara);
        string str=ara;
        str+=str;
        n*=2;
        for(int i=0;i<n;i++)
        {
            position[i]=str[i]-'a';
        }

        for(int steep=1;steep<n;steep*=2)
        {
            vector<data>v(n);
            for(int i=0;i<n;i++)
            {
                int a=position[i];
                int b;
                if(i+steep>=n)
                    b=100000000;
                else
                    b=position[i+steep];
                v[i].rank=pii(a,b);
                v[i].pos=i;
            }

            sort(all(v),cmp);

            position[v[0].pos]=0;
            suffix_ara[0]=v[0].pos;

            for(int i=1;i<n;i++)
            {
                suffix_ara[i]=v[i].pos;
                if(v[i].rank==v[i-1].rank)
                    position[v[i].pos]=position[v[i-1].pos];
                else
                    position[v[i].pos]=i;
            }
        }

        for(int i=0;i<n;i++)
        {
            if(suffix_ara[i]<n/2)
            {
                pf("%d\n",suffix_ara[i]);
//                pf("%s\n",str.substr(suffix_ara[i]).c_str());
                break;
            }
        }
    }

    return 0;
}

nCr%m when m is not prime and n and r is sufficiently large.

In many problems we need to calculate nCr%m where n, r and m are three positive integers. If the mod value m is a prime number then we can calculate nCr%m in different ways like using loops, using pascal’s triangle, using modular multiplicative inverse, using dp technique etc. This ways are described with source codes in this post.

Now our problem arrive when the mod value m is not prime. In this case we can’t use the above techniques. In this case we need to use the chinese remainder theorem (CRT) and Andrew Granville’s theory for calculating nCr. Here I provide you some ways to learn this techniques. I think this ways will be helpful to you.

1. First learn about chinese remainder theorem (CRT). You can learn it form these sources-
a. geeksforgeeks 1
b. geeksforgeeks 2
c. youtube 1
d. youtube 2

2. Second you can have a look on Andres Granville’s theory. The theory is explained here.

3. Now you can have a look on this problem. The detailed algorithm for our job is explained in this problem’s editorial section.

4. Now you can try to implement the algorithm. If you find any difficulties after several tries then you can see my implementation. Which is given below.


#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 LINE_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));}
//------------------------------------------------

#define mx 1000006

bitset<mx/2>vis;
vector<int>prime;

vector<pii>factor;

void sieve()
{
    int x=mx/2,y=sqrt(mx)/2;
    for(int i=1; i<=y; i++)
    {
        if(vis[i]==0)
        {
            for(int j=i*(i+1)*2; j<x; j+=(2*i)+1)
                vis[j]=1;
        }
    }

    prime.pb(2);

    for(int i=3; i<mx; i+=2)
        if(vis[i/2]==0)
            prime.pb(i);

}

ll factorial[mx];
ll arr[mx];


vector<ll>ans;

void precal(ll p, ll q, ll mod)
{
    arr[0]=1;
    arr[1]=1;
//    ll mod=bigmod(p,q,MOD);
    ll x=1;
    for(ll i=2; i<=mod; i++)
    {
        if(i%p)
            x=i;
        else
            x=1;
        arr[i]=(arr[i-1]*x)%mod;
    }
}

ll bigmod(ll n, ll p, ll mod)
{
    ll ret=1;
    while(p)
    {
        if(p%2)
            ret=(ret*n)%mod;
        n=(n*n)%mod;
        p/=2;
    }
    return ret;
}

ll E(ll n, ll p)
{
    ll ret=0;
    while(n)
    {
        ret+=n/p;
        n=n/p;
    }
    return ret;
}

ll f(ll n, ll mod)
{
    ll ret=bigmod(arr[mod-1],n/mod,mod)*arr[n%mod];
    return ret;
}

ll F(ll n, ll mod, ll p)
{
    ll ret=1;
    ll i=1;
    while(i<=n)
    {
        ret=(ret*f(n/i,mod))%mod;
        i=i*p;
    }
    return ret;
}

int inv(int a, int m) // Calculating Modular Multiplicative Inverse
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

//     Apply extended Euclid Algorithm
    while (a > 1)
    {
//         q is quotient
        q = a / m;

        t = m;

//         m is remainder now, process same as
//         euclid's algo
        m = a % m, a = t;

        t = x0;

        x0 = x1 - q * x0;

        x1 = t;
    }

//     Make x1 positive
    if (x1 < 0)
        x1 += m0;

    return x1;
}




ll nCr(ll n, ll r, ll p, ll mod)
{
    ll e=E(n,p)-E(r,p)-E(n-r,p);
    ll mod1=F(n,mod,p);
    ll mod2=(F(r,mod,p)*F(n-r,mod,p))%mod;
    mod2=inv(mod2,mod);
    ll ret=bigmod(p,e,mod);
    ret*=mod1;
    ret%=mod;
    ret*=mod2;
    ret%=mod;
    return ret;
}

ll findMinX(int k) // Chinese Remainder
{
    ll prod = 1;
    vector<int>num;
    for(int i=0; i<k; i++)
    {
        num.pb(bigmod(factor[i].ff,factor[i].ss,MOD));
    }
    for (int i = 0; i < k; i++)
        prod *= num[i];

    ll result = 0;

    for (int i = 0; i < k; i++)
    {
        ll pp = prod / num[i];
        result += ans[i] * inv(pp, num[i]) * pp;
    }

    return result % prod;
}

ll nCr_mod_m(ll n, ll r, ll m)
{
    factor.clear();
    ans.clear();
    int root=sqrt(m);
    ll mm=m;
    for(int i=0; i<SZ(prime) && prime[i]<=root; i++)
    {
        if(mm%prime[i]==0)
        {
            int cnt=0;
            while(mm%prime[i]==0)
            {
                mm/=prime[i];
                cnt++;
            }
            factor.pb(pii(prime[i],cnt));
            root=sqrt(mm);
        }
    }

    if(mm>1)
        factor.pb(pii(mm,1));



    for(int i=0; i<SZ(factor); i++)
    {
        ll p=factor[i].ff;

        ll num=bigmod(p,factor[i].ss,MOD);
        precal(p,factor[i].ss,num);
        ans.pb(nCr(n,r,p,num));
    }

    ll anss=findMinX(SZ(factor));
    return anss;
}

int main()
{

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

    sieve();

    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll n,r,m;
        cin>>n>>r>>m;

        ll ans=nCr_mod_m(n,r,m);

        pf("%lld C %lld mod %lld = %lld\n",n,r,m,ans);
    }

    return 0;
}


Practice problems:
1. nCr
2. Codechef’s Long Sandwich(SANDWICH).

SPOJ KALTSUM – k Alternating Sum

Problem Link : http://www.spoj.com/problems/KALTSUM/

Solution Idea:

Break the problem into two cases: When k is greater than sqrt(n) and when k is less tahn or equal sqrt(n). Deal with them in different ways.

Case 1: For any k>sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query.

Case 2: Now when k <= sqrt(n), you need to do some preprocessing.

let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1).

This solution idea is from this link.


#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 LINE_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));}
/*------------------------------------------------*/

ll dp[318][100005];
ll csum[100005];
ll ara[100005];

int main()
{

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

    int n,q;

    sff(n,q);
    for(int i=1;i<=n;i++)
    {
        sfl(ara[i]);
        csum[i]=csum[i-1]+ara[i];
    }

    int root=ceil(sqrt(n));

    for(int i=1;i<=root;i++)
    {
        ll temp=0,sub=0;
        for(int j=n;j>=1;j--)
        {
            temp+=ara[j];
            if(j+i>n)
                sub=0;
            else
                sub=ara[j+i];
            temp-=sub;

            if(j+i-1>n)
                dp[i][j]=0;
            else
                dp[i][j]=temp-dp[i][j+i];
        }
    }
//
//    for(int i=1;i<=root;i++,cout<<endl)
//        for(int j=1;j<=n;j++)
//        cout<<dp[i][j]<<" ";

    while(q--)
    {
        int a,b,k;
        sfff(a,b,k);
        ll ans=0;
        if(k>root)
        {
            for(int i=a,j=0;i<=b;i+=k,j++)
            {
                if(j%2==0)
                    ans+=csum[i+k-1]-csum[i-1];
                else
                    ans-=csum[i+k-1]-csum[i-1];
            }
            pf("%lld\n",ans);
        }
        else
        {
            int turn=(b-a+1)/k;
            if(turn%2==1)
                pf("%lld\n",dp[k][a]+dp[k][b+1]);
            else
                pf("%lld\n",dp[k][a]-dp[k][b+1]);
        }
    }


    return 0;
}


SPOJ: AMR10E – Stocks Prediction

Problem Link : http://www.spoj.com/problems/AMR10E/


#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 LINE_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= 1000000007;

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

    matrix()
    {
        row=col=0;
        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---------------------*/

matrix identity;

matrix func(matrix m, ll p)
{
//    if(p==0) return identity;
    if(p==1) return identity;
//
//    matrix ret=func(m,p/2);
//
//    matrix temp=m.pow(p/2);

    if(p%2==0)
    {
        return func(m,p/2)*(identity+m.pow(p/2));
    }
    else
    {
        return func(m,p-1)+m.pow(p-1);
    }
}

ll s[15],ara[15];

int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll n,r,k;

        sfffl(n,r,k);

        matrix base(r,1);

        ms(s,0);
        ms(ara,0);

        for(int i=1; i<=r; i++)
            sfl(s[i]);

        matrix a(r,r);

        for(int i=0; i<r; i++)
        {
            sfl(a.mat[0][i]);
            ara[i+1]=a.mat[0][i];
            if(i+1!=r)
                a.mat[i+1][i]=1;
        }

//        base.show();

//        a.show();

        a=a.pow(k);

//        a.show();

//        base.show();

        identity=a.identity();

        a=func(a,n);

//        a.show();

        ll ans=0;

        if(k>r)
        {
            for(int i=r+1; i<=k; i++)
            {
                for(int j=1; j<=r; j++)
                {
                    s[i]+=s[i-j]*ara[j];
                    s[i]%=MOD;
                }
            }

            for(int i=0; i<r; i++)
            {
                ans=(ans+(s[k-i]*a.mat[0][i])%MOD);
                ans%=MOD;

            }

        }
        else
        {
            for(int i=0; i<r; i++)
            {
                ans=(ans+(a.mat[r-k][r-i-1]*s[i+1])%MOD);
                ans%=MOD;
            }

        }
        pf("%lld\n",ans);

    }

    return 0;
}

UVa 11246 – K-Multiple Free set

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

Solution Idea:


int MFS(int N,int K)
{
int ret=0;
for(int i=1;N;i=-i)
{
ret+=N*i;
N/=K;
}
return ret;
}

So how does this work? Let us start with the full set {1…N}. We need to remove some numbers from this so that it is a K-multiple free set. For this, let us remove every multiple of K from the set. These are the numbers K,2K… and there are N/K of them. Removing them gives us a K-multiple free set. But we have removed some numbers unnecessarily. Since we already removed K, removing K² was unnecessary. Thus we can put back K²,2K²…, which would be N/K² numbers in total. But this ends up putting both K² and K³ into the set and we need to remove all multiples of K³ now. Proceeding in this fashion, it is easy to see that the cardinality of the final set is N – N/K + N/K² – N/K³…

In general, an input size of N=10⁹ in a mathematical problem should give you the idea that neither the time or space complexity of the solution can be O(N) and you have to come up with some sort of a closed form solution.

This solutino idea is from this link.


#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 LINE_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));}
/*------------------------------------------------*/


int main()
{

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

    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll n,k;
        sffl(n,k);
        if(k==0)
            pf("0\n");
        else
        {
            ll ans=n;
            ll kk=k;
            int cnt=1;
            while(kk<=n)
            {
                if(cnt%2)
                    ans-=(n/kk);
                else
                    ans+=(n/kk);
                kk*=k;
                cnt++;
            }
            pf("%lld\n",ans);
        }
    }

    return 0;
}