304 North Cardinal St.
Dorchester Center, MA 02124

# Polynomial Partition Function CodeChef Solution

## Polynomial Partition Function CodeChef Solution in C++14

``````#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
unsigned long long overflow_delta = 0;
int n;

inline void mult(int* a, int* b, int* c) {
for(int j = 0; j <= n; j++) {
long long tmp = 0;

for(int k = 0; k <= j; k++) {
tmp += (long long)a[k] * b[j-k];
if(tmp < 0) tmp += overflow_delta, assert(tmp >= 0);
}

c[j] = tmp%MOD;
}
}

int main() {
int t;
scanf("%d", &t);

// This ensures that the modulo remains meaningful in case of overflow
overflow_delta = (((1LL<<63)-1)%MOD -
((1LL<<63)-1+MOD)%MOD + MOD)%MOD;

// And this will fix it so that it remains positive, so we know when to
// apply the first fix
overflow_delta += ((1ULL<<63)+MOD)/MOD * MOD;

while(t--) {
int m, x;
int d, p[11];

scanf("%d %d %d %d", &m, &n, &x, &d);
for(int i = 0; i <= d; i++)
scanf("%d", &p[i]);

int mul = 0;
int pol[2][1024];
int cur[2][1024];
for(int i = 0; i <= n; i++) {
pol[0][i] = 0;
for(int j = d; j >= 0; j--)
pol[0][i] = ((long long)pol[0][i]*mul + p[j]) % MOD;
mul += x; if(mul >= MOD) mul -= MOD;
}

int *ccur = cur[0], *cpow = pol[0];
int *pcur = cur[1], *ppow = pol[1];

bool first = true;

while(m) {
if(m & 1) {
if(first) memcpy(pcur, cpow, sizeof(int) * 1024), first = false;
else mult(ccur, cpow, pcur);
swap(pcur, ccur);
}
if(m >>= 1) {
mult(cpow, cpow, ppow);
swap(ppow, cpow);
}
}

printf("%d\n", ccur[n]);
}
}``````

## Polynomial Partition Function CodeChef Solution in C

``````#include<stdio.h>
#define M 1000000007

int main()
{
int i,j,k,t,m,n,d,step[25],s;
long long A[401][801];
long long P[801],C[15],x,X;

scanf("%d",&t);

while(t--)
{
scanf("%d",&m);
scanf("%d",&n);
scanf("%lld",&x);

scanf("%d",&d);
X=1;
for(i=0;i<=d;i++)
{
scanf("%lld",&C[i]);
C[i]=(C[i]*X)%M;
X=(X*x)%M;
}//o(d)

for(i=0;i<=n;i++)
{
P[i]=C[0];
X=i;
for(j=1;j<=d;j++)
{
P[i]=(P[i]+(C[j]*X))%M;
X=(X*i)%M;
}
A[1][i]=P[i];
//	if(A[1][i]<0)
//printf("i%d %lld \n",i, A[1][i]);
}/// o(nd)
//printf("\n");

j=m;
for(i=0;j;i++)
{
if(j%2)
{
step[i]=0;
j--;
}
else
{
step[i]=1;
j/=2;
}
//printf("STEP:%d %d \n",j,step[i]);
}
s=i-2;

//break;

i=1;
for(;s>=0;s--)
{
//printf("k%d i%d step[k]%d\n",s,i,step[s]);
if(step[s]==0)
{;
i=i+1;
for(j=0;j<=n;j++)
{
A[i][j]=0;
for(k=0;k<=j;k++)
{
A[i][j]=(A[i][j]+(P[k]*A[i-1][j-k])%M)%M;
}
A[i][j]=A[i][j]%M;
}
}
else
{
i=i*2;
for(j=0;j<=n;j++)
{
A[i][j]=0;
for(k=0;k<=j;k++)
{
A[i][j]= (A[i][j]+(A[i/2][k]*A[i/2][j-k])%M)%M;
}
A[i][j]=A[i][j]%M;
}

}
//	if(A[i][j]<0)
//printf("i%d j%d %lld \n",i,j,A[i][j]);

}//o(mn2)

printf("%lld\n",A[m][n]);
}

return 0;
}``````

## Polynomial Partition Function CodeChef Solution in JAVA

``````import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main
{
public static void main(String args[])
{
final int MOD = 1000000007;

int T = cin.nextInt();
for (; T > 0; --T)
{
int m = cin.nextInt(),
n = cin.nextInt(),
X = cin.nextInt();

int d = cin.nextInt();
int c[] = new int[d+1];

for (int i = 0; i <= d; ++i)
c[i] = cin.nextInt();

/*
* f[i, j] = sigmak( f[i-1, k] * F((j-k)X) )
* 		   = sigmak( f[i-1, k] * [ c[0] * (j-k)X^0 + c[1] * (j-k)X^1 + .. + c[d] * (j-k)X^d ] )
* 		   = sigmak( f[i-1, k] * sigmau(c[u] * (j-k)X^u) )
* 		   = sigmak( f[i-1, k] * sigmau(c[u] * x^u * sigmav( C(u, v) * (-k)^v * j^(u-v) ) ) )
* 		   = sigmau( c[u] * x^u  * sigmav( C(u, v) * j^(u-v) * sigmak(f[i-1, k] * (-k)^v) ) )
* 		   = sigmav( sigmak(f[i-1, k] * (-k)^v) * sigmau( c[u] * x^u * C(u, v) * j^(u-v) ) )
* 			 with u >= v
*/

int C[][] = new int[d+1][d+1];
for (int i = 0; i <= d; ++i)
C[i][0] = C[i][i] = 1;
for (int i = 1; i <= d; ++i)
for (int j = 1; j < i; ++j)
{
C[i][j] = C[i-1][j] + C[i-1][j-1];
if (C[i][j] >= MOD) C[i][j] -= MOD;
}

int power[][] = new int[n+1][d+1];
for (int i = 0; i <= n; ++i)
power[i][0] = 1;
for (int i = 0; i <= n; ++i)
for (int j = 1; j <= d; ++j)
power[i][j] = (int) (power[i][j-1] * (long)i % MOD);

int npower[][] = new int[n+1][d+1];
for (int i = 0; i <= n; ++i)
npower[i][0] = 1;
for (int i = 0; i <= n; ++i)
for (int j = 1; j <= d; ++j)
{
npower[i][j] = (int) (npower[i][j-1] * (long)(-i) % MOD);
if (npower[i][j] < 0)
npower[i][j] += MOD;
}

int xpow[] = new int[d+1];
xpow[0] = 1;
for (int i = 1; i <= d; ++i)
xpow[i] = (int)( (long)xpow[i-1] * X % MOD);

int coff[][] = new int[n+1][d+1];
for (int k = 0; k <= n; ++k)
{
for (int i = 0; i <= d; ++i)
{
coff[k][i] = 0;
for (int j = i; j <= d; ++j)
{
int tmp = (int) (c[j] * (long) xpow[j] % MOD * C[j][i] % MOD * power[k][j-i] % MOD);
coff[k][i] += tmp;
if (coff[k][i] >= MOD)
coff[k][i] -= MOD;
}
}
}

int dp[][] = new int[m+1][n+1];
int sum[][][] = new int[m+1][n+1][d+1];

dp[0][0] = 1;
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= d; ++j)
{
sum[0][i][j] = (int) ((dp[0][i] * (long) npower[i][j]) % MOD);
if (i > 0)
sum[0][i][j] += sum[0][i-1][j];
if (sum[0][i][j] >= MOD)
sum[0][i][j] += MOD;
}
}
for (int i = 1; i <= m; ++i)
for (int j = 0; j <= n; ++j)
{
dp[i][j] = 0;
for (int k = 0; k <= d; ++k)
{
dp[i][j] += (int) (sum[i-1][j][k] * (long) coff[j][k] % MOD);
if (dp[i][j] >= MOD)
dp[i][j] -= MOD;
}
for (int k = 0; k <= d; ++k)
{
sum[i][j][k] = (int) (dp[i][j] * (long) npower[j][k] % MOD);
if (j > 0)
sum[i][j][k] += sum[i][j-1][k];
if (sum[i][j][k] >= MOD)
sum[i][j][k] -= MOD;
}
}
System.out.println(dp[m][n]);
}
}
}

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

this.stream = stream;
}

if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

while (isSpaceChar(c))
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}

public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
} ``````

## Polynomial Partition Function CodeChef Solution in C#

``````using System;

public class PARPOlY
{
public static void Main(string[] args)
{
for (int i = 1; i <= testCases; ++i)
solve();
}

public static long MOD = 1000000007L;

public static void solve()
{
string[] s1 = Console.ReadLine().Split(new char[]{' '});
int m = int.Parse(s1[0]);
int n = int.Parse(s1[1]);
long x = long.Parse(s1[2]);

string[] s2 = Console.ReadLine().Split(new char[] { ' ' });
int d = int.Parse(s2[0]);
long[] c = new long[d + 1];
for (int i = 0; i < c.Length; ++i)
c[i] = long.Parse(s2[i + 1]);

long[] P = getPolynomialValues(n, x, c);
long[] M = raise(P, m);

Console.WriteLine(M[n]);
}

public static long[] getPolynomialValues(int n, long _x, long[] c)
{
long[] P = new long[n + 1];
for (int i = 0; i <= n; ++i)
{
P[i] = 0L;
long x = (i * _x) % MOD;
for (int j = 0; j < c.Length; ++j)
{
P[i] = ((P[i] * x) % MOD + c[c.Length - j - 1]) % MOD;
}
}
return P;
}

public static long[] raise(long[] M, int exponent)
{
if (exponent == 1) return M;
long[] _M = raise(M, exponent >> 1);
_M = convolute(_M, _M);
if (exponent % 2 == 1) _M = convolute(_M, M);
return _M;
}

public static long[] convolute(long[] a, long[] b)
{
long[] res = new long[a.Length];
for (int i = 0; i < res.Length; ++i)
{
res[i] = 0L;
for (int j = 0; j <= i; ++j)
{
res[i] = (res[i] + (a[j] * b[i - j]) % MOD) % MOD;
}
}
return res;
}
}``````
##### Polynomial Partition Function CodeChef Solution Review:

In our experience, we suggest you solve thisPolynomial Partition Function 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 Polynomial Partition Function CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Polynomial Partition Function 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!