Category Archives: Algorithm

Source code of specific algorithm

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

1
Posted on by

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).

DFS Sample Code

0
Posted on by 

#include <bits/stdc++.h>

using namespace std;

vector<int>v[100];
bool visited[100];

int node,edge;

void DFS(int n)
{
    visited[n]=true;
    cout<<n<<" ";
    int temp;
    for(int i=0; i<v[n].size(); i++)
    {
        temp=v[n][i];
        if(!visited[temp])
            DFS(temp);
    }
}


int main()
{
    cin>>node>>edge;
    for(int i=0; i<edge; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int src,dst;
    cin>>src>>dst;
    memset(visited,0,sizeof visited);
    cout<<"DFS traverse order is = ";
    DFS(src);
    cout<<endl;
    if(visited[dst])
        cout<<dst<<" is reachable from "<<src<<endl;
    else
        cout<<dst<<" is not reachable from "<<src<<endl;
    return 0;
}

BFS Sample Code

0
Posted on by 

#include <bits/stdc++.h>

using namespace std;

vector<int>G[100]; // Here 100 is maximum number of Nodes.
bool visited[100];
int parent[100]; // This is used to print path from source to distance
int dis[100];
int node,edge;

void path_print(int u)
{
    if(u==-1) return;
    path_print(parent[u]);
    printf("%d ",u);
}

void bfs(int src)
{
    queue<int>Q;
    Q.push(src);
    dis[src]=0;
    parent[src]=-1;
    memset(visited,0,sizeof visited);
    visited[src]=1 ;

    while(!Q.empty())
    {
        int u=Q.front();
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(!visited[v])
            {
                dis[v]=dis[u]+1 ;
                parent[v]=u;
                visited[v]=1 ;
                Q.push(v);
            }
        }
        Q.pop();
    }
    for(int i=1 ; i<=node; i++)
    {
        printf("%d to %d distance = %d\n",src,i,dis[i]);
        printf("Path = ");
        if(visited[i])
        path_print(i);
        printf("\n");
    }
}

int main()
{
    cin>>node>>edge;
    for(int i=1; i<=edge; i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int src;
    cin>>src;
    bfs(src);
    return 0;
}

Light OJ : 1212 – Double Ended Queue

0
Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1212


/*
MMP""MM""YMM   db      `7MN.   `7MF'`7MMM.     ,MMF' .g8""8q.`YMM'   `MM'
P'   MM   `7  ;MM:       MMN.    M    MMMb    dPMM .dP'    `YM.VMA   ,V
     MM      ,V^MM.      M YMb   M    M YM   ,M MM dM'      `MM VMA ,V
     MM     ,M  `MM      M  `MN. M    M  Mb  M' MM MM        MM  VMMP
     MM     AbmmmqMA     M   `MM.M    M  YM.P'  MM MM.      ,MP   MM
     MM    A'     VML    M     YMM    M  `YM'   MM `Mb.    ,dP'   MM
   .JMML..AMA.   .AMMA..JML.    YM  .JML. `'  .JMML. `"bmmd"'   .JMML.
*/


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <string>
#include <map>

#define pii pair <int,int>
#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 oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d:\n",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    getint(t);
    list <int>l;
    TEST_CASE(t)
    {
        int n,m;
        getint(n);
        getint(m);
        string str;
        int num;
        PRINT_CASE;
        while(m--)
        {
            cin>>str;
            if(str=="pushLeft")
            {
                getint(num);
                if(l.size()==n)
                {
                    cout<<"The queue is full"<<endl;
                }
                else
                {
                    l.push_front(num);
                    pf("Pushed in left: %d\n",num);
                }
            }

            else if(str=="pushRight")
            {
                getint(num);
                if(l.size()==n)
                {
                    cout<<"The queue is full"<<endl;
                }
                else
                {
                    l.push_back(num);
                    pf("Pushed in right: %d\n",num);
                }
            }
            else if(str=="popLeft")
            {
                if(l.empty())
                {
                    cout<<"The queue is empty"<<endl;
                }
                else
                {
                    pf("Popped from left: %d\n",l.front());
                    l.pop_front();
                }
            }
            else if(str=="popRight")
            {
                if(l.empty())
                {
                    cout<<"The queue is empty"<<endl;
                }
                else
                {
                    pf("Popped from right: %d\n",l.back());
                    l.pop_back();
                }
            }

        }
        l.clear();
    }
    return 0;
}

Articulation Point

0
Posted on by 

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#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             100007
#define MAX             100007
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(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 all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long


using namespace std;

vector<int>graph[MAX];
int n,m,cnt;
bool visited[MAX],artpoint[MAX];
int back_edge[MAX],dis[MAX],degroot,dfsnum,root;

void Find_Art(int u)
{
    visited[u]=1;
    dfsnum++;
    back_edge[u]=dis[u]=dfsnum;
    loop(i,SZ(graph[u]))
    {
        int v=graph[u][i];
        if(!visited[v])
        {
            Find_Art(v);
            if(u==root)
            {
                degroot++;
                if(degroot>=2)
                {
                    artpoint[root]=1;
                }
            }

            back_edge[u]=min(back_edge[u],back_edge[v]);
            if(back_edge[v]>=dis[u] && u!=root)
            {
                artpoint[u]=1;
            }

        }
        else
            back_edge[u]=min(back_edge[u],dis[v]);
    }
}

void allclear()
{
    loop(i,n+5)
    {
        graph[i].clear();
        visited[i]=0;
        artpoint[i]=0;
        back_edge[i]=0;
        dis[i]=0;
    }
    cnt=dfsnum=degroot=0;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sff(n,m);
        allclear();
        int a,b;
        loop(i,m)
        {
            sff(a,b);
            graph[a].pb(b);
            graph[b].pb(a);
        }

        root=1;
        Find_Art(1);

        REP(i,1,n+1)
        if(artpoint[i]) cnt++;
        PRINT_CASE;
        cout<<cnt<<endl;
    }
    return 0;
}

Strongly Connected Component (SCC Kosaraju)

0
Posted on by 

#include <bits/stdc++.h>

using namespace std;

vector<int>G[50],G_reverse[50];
int finishing_time,finish[50],visited[50];

int DFS(int n)
{
    finishing_time++;
    int i,j,k;
    visited[n]=1;
    for(i=0,j=G[n].size(); i<j; i++)
    {
        k=G[n][i];
        if(visited[k]==0)
            DFS(k);
    }
    finish[n]=++finishing_time;
    return 0;
}

int dfs2(int n)
{
    printf(" %d",n);
    visited[n]=1;
    int i,j,k;
    for(i=0,j=G_reverse[n].size(); i<j; i++)
    {
        k=G_reverse[n][i];
        if(visited[k]==0)
            dfs2(k);
    }
    return 0;
}

int main()
{
    int i,j,k,m,n,e;
    printf("Enter no of nodes in the graph:");
    cin>>n;
    printf("Enter no of edges in the graph:");
    cin>>e;
    
    while(e--)
    {
        cin>>i>>j;
        G[i].push_back(j);
        G_reverse[j].push_back(i);
    }
    
    memset(visited,0,sizeof visited);
    finishing_time=0;
    
    for(i=1; i<=n; i++)
    {
        if(visited[i]==0)
        {
            DFS(i);
        }
    }
    
    vector<pair<int,int> >v;
    
    for(i=1; i<=n; i++)
    {
        v.push_back(make_pair(finish[i],i));
    }
    
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());//sorting in ascending order.
    
    int SCC=0;
    
    memset(visited,0,sizeof visited);
    
    for(i=0; i<n; i++)
    {
        m=v[i].second;
        if(!visited[m])
        {
            printf("Component of SCC no %d:",++SCC);
            dfs2(m);
            printf("\n");
        }
    }
    
    return 0;
}

Minimum Spanning Tree (Kruskal)

0
Posted on by 

#include <bits/stdc++.h>

#define MAXN 100000

using namespace std;

struct edge
{
    int u,v,w;
    bool operator < ( const edge& p ) const
    {
        return w < p.w;
    }
};

int pr[MAXN];
vector<edge>e;

int find(int r)
{
    return pr[r]= (pr[r]==r) ? r:  find(pr[r]);
}

int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1; i<=n; i++)pr[i]=i;

    int count=0,s=0;
    for(int i=0; i<(int)e.size(); i++)
    {
        int u=find(e[i].u);
        int v=find(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            count++;
            s+=e[i].w;
            if(count==n-1) break;
        }
    }
    return s;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edge get;
        get.u=u;
        get.v=v;
        get.w=w;
        e.push_back(get);
    }
    cout<<mst(n)<<endl;
    return 0;
}

Segment Tree

0
Posted on by 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>

#define ll long long
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)

#define MAX 1000
using namespace std;

int ara[MAX];
int tree[MAX*3];

void init(int node,int b,int e)
{
    if(b==e)
       {
         tree[node]=ara[b];
         return;
       }
    int mid=(b+e)/2;
    int left=2*node;
    int right=2*node+1;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=tree[left]+tree[right];
}

int query(int node,int b,int e,int i, int j)
{
    if(i>e || j<b)
        return 0;
    if(b>=i && e<=j)
        return tree[node];
    int left=node*2;
    int right=node*2+1;
    int mid=(b+e)/2;
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    return p1+p2;
}

void update(int node,int b,int e, int i, int new_value)
{
    if(i>e || i<b)
        return;
    if(b>=i && e<=i)
    {
        tree[node]=new_value;
        return;
    }
    int left=node*2;
    int right=node*2+1;
    int mid=(b+e)/2;
    update(left,b,mid,i,new_value);
    update(right,mid+1,e,i,new_value);
    tree[node]=tree[left]+tree[right];
}

int main()
{
    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>ara[i];
    init(1,1,n);
    cout<<query(1,1,n,1,4)<<endl;
    update(1,1,n,2,0);
    cout<<query(1,1,n,2,2)<<endl;
    update(1,1,n,2,1);
    cout<<query(1,1,n,2,3)<<endl;
    return 0;
}

KMP (knuth morris pratt)

0
Posted on by 

/*
MMP""MM""YMM   db      `7MN.   `7MF'`7MMM.     ,MMF' .g8""8q.`YMM'   `MM'
P'   MM   `7  ;MM:       MMN.    M    MMMb    dPMM .dP'    `YM.VMA   ,V
     MM      ,V^MM.      M YMb   M    M YM   ,M MM dM'      `MM VMA ,V
     MM     ,M  `MM      M  `MN. M    M  Mb  M' MM MM        MM  VMMP
     MM     AbmmmqMA     M   `MM.M    M  YM.P'  MM MM.      ,MP   MM
     MM    A'     VML    M     YMM    M  `YM'   MM `Mb.    ,dP'   MM
   .JMML..AMA.   .AMMA..JML.    YM  .JML. `'  .JMML. `"bmmd"'   .JMML.
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#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 oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 1000007
#define CIN ios_base::sync_with_stdio(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

/* Bits operation */
int Set(int n,int pos)  { return n = n | 1<<pos;}
bool check(int n,int pos) { return n & 1<<pos;}
int Reset(int n, int pos) { return n=n & ~(1<<pos);}
/*----------------*/

 int lps[MAX];

 void computePrefixFunction(string P)
 {
     int n=SZ(P);
     int k=-1;
     lps[0]=-1;
     for(int i=1;i<n;i++)
     {
         while(k>-1 && P[i]!=P[k+1])
            k=lps[k];
         if(P[i]==P[k+1])
            k++;
         lps[i]=k;
     }
 }

 void KMP(string& T, string& P)
 {
     int m=SZ(P);
     int n=SZ(T);
     computePrefixFunction(P);
     int k=-1;
     for(int i=0;i<n;i++)
     {
         while(k>-1 && T[i]!=P[k+1])
            k=lps[k];
         if(T[i]==P[k+1])
            k++;
         if(k==m-1)
         {
             cout<<"Pattern found in position "<<i-k<<endl;
             k=lps[k];
         }
     }
 }

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    string text,pattarn;
    while(cin>>text>>pattarn)
    {
        KMP(text,pattarn);
    }
    return 0;
}

Binary Indexed Tree (BIT)

0
Posted on by 

#include <bits/stdc++.h>

using namespace std;

int a[100000],tree[100000];

int query(int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=tree[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

void update(int idx, int x, int n)
{
    while(idx<=n)
    {
        tree[idx]+=x;
        idx += idx & (-idx);
    }
}

int main ()
{
    int tc,n,q,cas=0;
    cin>>tc;
    while(tc--)
    {
        printf("Case %d:\n",++cas);
        cin>>n>>q;
        memset(tree,0,sizeof tree);
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            update(i,a[i],n);
        }
        int ic,idx,v,x,y;
        for(int i=0; i<q; i++)
        {
            cin>>ic;
            if(ic==1)
            {
                cin>>idx;
                idx++;
                update(idx,-a[idx],n);
                printf("%d\n",a[idx]);
                a[idx]=0;
            }

            else if(ic==2)
            {
                cin>>idx>>v;
                idx++;
                update(idx,v,n);
                a[idx]+=v;
            }

            else
            {
                cin>>x>>y;
                printf("%d\n",query(y+1)-query(x));
            }
        }

    }
    return 0;
}