Counting Terms CodeChef Solution

Problem -Counting Terms 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.

Counting Terms CodeChef Solution in C++14

#include <bits/stdc++.h>
using namespace std;
const int N=2e9+7; 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
typedef long long ll;
//          ▄              ▄    
//         ▌▒█           ▄▀▒▌   
//         ▌▒▒█        ▄▀▒▒▒▐   
//        ▐▄█▒▒▀▀▀▀▄▄▄▀▒▒▒▒▒▐   
//      ▄▄▀▒▒▒▒▒▒▒▒▒▒▒█▒▒▄█▒▐   
//    ▄▀▒▒▒░░░▒▒▒░░░▒▒▒▀██▀▒▌   
//   ▐▒▒▒▄▄▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▀▄▒▌  
//   ▌░░▌█▀▒▒▒▒▒▄▀█▄▒▒▒▒▒▒▒█▒▐  
//  ▐░░░▒▒▒▒▒▒▒▒▌██▀▒▒░░░▒▒▒▀▄▌ 
//  ▌░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒▌ 
// ▌▒▒▒▄██▄▒▒▒▒▒▒▒▒░░░░░░░░▒▒▒▐ 
// ▐▒▒▐▄█▄█▌▒▒▒▒▒▒▒▒▒▒░▒░▒░▒▒▒▒▌
// ▐▒▒▐▀▐▀▒▒▒▒▒▒▒▒▒▒▒▒▒░▒░▒░▒▒▐ 
//  ▌▒▒▀▄▄▄▄▄▄▒▒▒▒▒▒▒▒░▒░▒░▒▒▒▌ 
//  ▐▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░▒░▒▒▄▒▒▐  
//   ▀▄▒▒▒▒▒▒▒▒▒▒▒▒▒░▒░▒▄▒▒▒▒▌  
//     ▀▄▒▒▒▒▒▒▒▒▒▒▄▄▄▀▒▒▒▒▄▀   
//       ▀▄▄▄▄▄▄▀▀▀▒▒▒▒▒▄▄▀     
//          ▀▀▀▀▀▀▀▀▀▀▀▀       
 
const int mod = 1000003;
const int Maxd = 105;
const int Maxm = 60;

int fac[Maxd], inv[Maxd];
int t;
ll n, k;
int p;
int prec[Maxd];
int all[Maxm];
int my[Maxm];
int res;

int Inv(int a)
{
	int res = 1;
	int p = mod - 2;
	while (p) {
		if (p & 1) res = ll(res) * a % mod;
		p >>= 1; a = ll(a) * a % mod;
	}
	return res;
}

int C(ll n, int k)
{
	if (n < 0 || k < 0 || k > n) return 0;
	n %= mod;
	int res = 1;
	for (int i = 0; i < k; i++) {
		res = ll(res) * n % mod;
		n = (n - 1 + mod) % mod;
	}
	return ll(res) * inv[k] % mod;
}

int main()
{
    IOS;
	fac[0] = inv[0] = 1;
	for (int i = 1; i < Maxd; i++) {
		fac[i] = ll(i) * fac[i - 1] % mod;
		inv[i] = Inv(fac[i]);
	}
	scanf("%d", &t);
	while (t--) {
		scanf("%lld %lld %d", &n, &k, &p);
		for (int i = 0; i < p; i++)
			prec[i] = C(k - 1 + i, i);
		all[0] = 1;
		all[1] = 0;
		for (int i = 0; i < p; i++)
			all[1] = (all[1] + prec[i]) % mod;
		for (int i = 2; i < Maxm; i++)
			all[i] = ll(all[i - 1]) * all[1] % mod;
		fill(my, my + Maxm, 0);
		int pnt = 0;
		while (n) {
			my[pnt++] = n % p; n /= p;
		}
		int cur = 1;
		res = 0;
		for (int i = Maxm - 1; i >= 0; i--) {
			for (int j = 0; j < my[i]; j++)
				res = (res + ll(cur) * prec[j] % mod * all[i]) % mod;
			cur = ll(cur) * prec[my[i]] % mod;
		}
		res = (res + cur) % mod;
		printf("%d\n", res);
	}
	return 0;
}

Counting Terms CodeChef Solution in C

#include <stdio.h>
 
#define M 1000003
#define LL long long
 
int x[100];
 
int A(int a, int b){a+=b;return a>=M?a-M:a;}
int B(int a, int b){return (LL)a*b%M;}
 
int C(int b)
{
int a=M, y=1, yy=0, q, tmp, aa=a;
for(;b>1; q=a/b,tmp=a%b,a=b,b=tmp,tmp=y,y=yy-q*y,yy=tmp);
return y>0?y:aa+y;
}
 
main()
{
int fall, i, p, res, q;
int v[100], w[100];
long long n, k;
for(i=0; ++i<100; x[i]=C(i));
for(scanf("%d",&fall); fall--&&scanf("%lld %lld %d",&n,&k,&p); printf("%d\n",res))
	{
	for(n+=v[0]=!(i=w[0]=0); ++i<=p; w[i]=w[i-1]+v[i-1],v[i]=B(v[i-1], B((i+k-1)%M, x[i])));
	for(res=!(q=1); n; res=B(res,v[n%p]),res=A(res,B(q,w[n%p])),q=B(q,w[p]),n/=p);
	}
return 0;
}

Counting Terms CodeChef Solution in JAVA

import java.io.*;
import java.math.BigInteger;
import java.util.*;
 
public class Main implements Runnable {
 
	final static int MOD = 1000003;
 
	private void solve() throws IOException {
		precalc();
		int tests = nextInt();
		for (int i = 0; i < tests; i++) {
			onetest();
		}
	}
 
	void precalc() {
		inverse = new int[101];
		for (int i = 1; i < inverse.length; i++) {
			inverse[i] = BigInteger.valueOf(i)
					.modInverse(BigInteger.valueOf(MOD)).intValue();
		}
	}
 
	int[] inverse;
	long n, k;
	int p;
	int[] digits = new int[100];
	int cnt;
	int[] c = new int[100];
	int[] csum = new int[100];
 
	int[] d = new int[100];
 
	void getCs() {
		c[0] = 1;
		csum[0] = 0;
		csum[1] = 1;
		int k1 = (int) (k % MOD);
		for (int i = 1; i < p; i++) {
			long cur = (long) c[i - 1] * (k1 + i - 1);
			cur = cur * inverse[i] % MOD;
			c[i] = (int) cur;
			csum[i + 1] = (csum[i] + c[i]) % MOD;
		}
	}
 
	void getDigits() {
		cnt = 0;
		long n = this.n;
		while (n > 0) {
			digits[cnt++] = (int) (n % p);
			n /= p;
		}
	}
 
	private void onetest() {
		n = nextLong();
		k = nextLong();
		p = nextInt();
		getDigits();
		getCs();
		d[0] = 1;
		for (int i = 1; i < cnt; i++) {
			d[i] = (int) ((long) d[i - 1] * csum[p] % MOD);
		}
		long res = 0;
		long mul = 1;
		for (int i = cnt - 1; i >= 0; i--) {
			long cur = mul * csum[digits[i]] * d[i] % MOD;
			res += cur;
			mul = mul * c[digits[i]] % MOD;
		}
		res += mul;
		res %= MOD;
		out.println(res);
	}
 
	public static void main(String[] args) {
		new Thread(new Main()).start();
	}
 
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	boolean eof = false;
 
	public void run() {
		Locale.setDefault(Locale.US);
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(239);
		}
	}
 
	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return "0";
			}
		}
		return st.nextToken();
	}
 
	int nextInt() {
		return Integer.parseInt(nextToken());
	}
 
	long nextLong() {
		return Long.parseLong(nextToken());
	}
 
	double nextDouble() {
		return Double.parseDouble(nextToken());
	}
}

Counting Terms CodeChef Solution Review:

In our experience, we suggest you solve this Counting Terms 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 Counting Terms CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Counting Terms 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