icode_8990's blog

By icode_8990, history, 3 months ago, In English,

Hello, Newbie here. I am trying to solve this problem and this is the solution i am referring to:

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long num[100010],pw[100010];
int main()
{
	long long n,q,i,res,l,r;
	string s;
	cin>>n>>q;
	cin>>s;
	for(i=0;i<n;i++)
	{
		num[i+1] =num[i]+(s[i]=='0');
	}
	pw[0]=1;
	for(i=1;i<n+5;i++)
	{
		pw[i] = pw[i-1]*2;
		if(pw[i]>=mod) pw[i]-=mod;
	}
	while(q--)
	{
		scanf("%lld%lld",&l,&r);
		res=(mod+pw[r-l+1]-pw[num[r]-num[l-1]])%mod; 
		printf("%lld\n",res);
	}

	
	return 0;
}

I am trying to understand the modulo used here. why does he add another mod in res. How does it help?

Thanks!

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By icode_8990, history, 3 months ago, In English,

Hello,

I am trying to solve this problem . But I didn't get the combinatorics used in this solution .How did he conclude that there are (n+1)! states in total?. Also explain me this part:

After checking this game more accurately I can say that the longest path in the state-graph for n = 10 has length 106, so it is enough to do 106 fights, but solutions that did about 40 millions also passed.

Thank you!

Read more »

 
 
 
 

By icode_8990, history, 4 months ago, In English,

So in this problem i am trying to solve it using dynamic programming approach. But I am unable to understand the solution since its written in poor english. I am referring to this tutorial. How is the dp[][] being developed?. it will be great if someone could explain in details since i am a newbie. Thank you in advance!

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int mod = 1e9 + 7;

int dp[100][2];

void add(int &a, int b)
{
    a += b;
    if(a >= mod)
        a -= mod;
}

int main(int argc, char ** argv)
{
    int n, k, d;
    cin >> n >> k >> d;
    dp[0][0] = 1;
    dp[0][1] = 0;
    
    for(int i = 1 ; i <= n ; ++i)
    {
        dp[i][0] = dp[i][1] = 0;
        
        for(int j = 1 ; j <= k ; ++j)
        {
            if(i-j < 0) break;
            
            if(j < d)
            {
                add(dp[i][0], dp[i-j][0]);
                add(dp[i][1], dp[i-j][1]);
            }
            else
            {
                add(dp[i][1], dp[i-j][0]);
                add(dp[i][1], dp[i-j][1]);
            }
        }
    }
    cout << dp[n][1] << "\n";
    return 0;
}

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it