Colorful Chain CodeChef Solution

Problem -Colorful Chain CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

<<Previous CodeChef Problem Next Codechef Problem>>

Colorful Chain CodeChef Solution in C++14

#include<bits/stdc++.h>
#include<math.h>
#define rep(i,k,n) for(int i=k;i<n;i++)
#define ll long long
#define MOD 1000000007ll
#define ROD 1000000009ll
#define INF 1e18
#define MIN(a,b) (a>b?b:a)
using namespace std;
#define mp make_pair
#define pb push_back
#define  piii pair<pair<ll,ll>,ll>
#define pii pair<ll,ll>
#define fi first
#define se second
#define MAXN 200010
ll t,n,m,ar[MAXN],sr[MAXN],fac[MAXN];
ll func(ll);
int main()
{
	fac[0]=1;
	rep(i,1,MAXN)
	fac[i]=(fac[i-1]*i)%MOD;
	scanf("%lld",&t);
	while(t--)
	{
		rep(i,0,MAXN)
		ar[i]=sr[i]=0;
		scanf("%lld %lld",&n,&m);
		for(int i=2*n;i>n;i--)
		{
			sr[i]=sr[i+1]+1;
			ar[i]=1;
		}
		for(int i=n;i>=m+2;i--)
		{
			ar[i]=(sr[i+1]-sr[i+m+1]+MOD)%MOD;
			sr[i]=(ar[i]+sr[i+1])%MOD;
		}
		func(1);
		// rep(i,1,2*n+1)
		// cout<<ar[i]<<" ";
		// cout<<"\n";		
		printf("%lld\n",ar[1]);
	}
}
ll func(ll idx)
{
	//cout<<idx<<" "<<sr[idx]<<"\n";
	if(ar[idx]!=0)
		return ar[idx];
	if(idx==m+1)
		return 0;
	// cout<<"S"<<idx<<" "<<m-idx+1<<" "<<m+1-idx<<" "<<idx+m+1<<"\n";
	ar[idx]=((m-idx+1)*(fac[m+1-idx]*func(idx+m+1)%MOD+func(idx+1)))%MOD;

	//cout<<"D";
	sr[idx]=(ar[idx]+sr[idx+1])%MOD;
	return ar[idx];
}

Colorful Chain CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

ll dp[200000], sum[200000];
ll fact[200000];
int n, m;


ll solve(int n){
  int i,j,k;
  ll res = 0;

  if(n <= 0) return 1;
  if(dp[n] >= 0) return dp[n];

  rep(i,m) res = (res + solve(n-i-1))%M;

  return dp[n] = res;
}

int main(){
  int i,j,k,l, down, up;
  int size;
  ll res;

  fact[0] = 1;
  REP(i,1,200000) fact[i] = (fact[i-1]*i)%M;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&m);

    dp[0] = 1;
    sum[0] = 0; sum[1] = 1;
    REP(i,1,n+1){
      up = i - 1;
      down = i - m;

      dp[i] = 0;
      if(down < 0) dp[i] = -down, down = 0;

      dp[i] += sum[up+1] - sum[down];
      dp[i] %= M;
      if(dp[i] < 0) dp[i] += M;
      
      sum[i+1] = (sum[i] + dp[i])%M;
    }
    
    res = 0;
    rep(i,m){
      if(n-i-m-1 >= 0) res += (dp[n-i-m-1] * (m-i))%M;
      else             res += (m-i)%M;
    }
    res %= M;
    res = (res * fact[m])%M;

    res %= M;
    printf("%d\n",(int)res);
  }

  return 0;
}

Colorful Chain CodeChef Solution in JAVA

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static int mod = 1000000007;
	
	static void solve()
	{
		long[] fact = new long[100001];
		fact[0] = 1;
		for(int i = 1;i <= 100000;i++){
			fact[i] = fact[i-1] * i % mod;
		}
		
		for(int T = ni();T >= 1;T--){
			int n = ni(), m = ni();
			int[] a = new int[n];
			a[0] = m;
			for(int i = 0;i < m;i++){
				a[i] = m-i;
			}
			int s = 0;
			int tot = 0;
			for(int i = 0;i < n;i++){
				a[i] = (a[i]+s)%mod;
				if(i >= n-m-1){
					tot = (tot + a[i]) % mod;
				}
				if(i < n-m-1){
					s += a[i];
					s %= mod;
				}
				if(i >= m){
					s += (mod-a[i-m]);
					s %= mod;
				}
			}
			out.println(tot*fact[m]%mod);
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	static boolean eof()
	{
		try {
			is.mark(1000);
			int b;
			while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}
		
	static int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Colorful Chain CodeChef Solution Review:

In our experience, we suggest you solve this Colorful Chain CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Colorful Chain CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Colorful Chain CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn