304 North Cardinal St.
Dorchester Center, MA 02124

# Colorful Chain CodeChef Solution

## 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!