Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Polynomial Partition Function CodeChef Solution
Problem -Polynomial Partition Function 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.
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[])
{
InputReader cin = new InputReader(System.in);
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]);
}
}
}
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
c = read();
} 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)
{
int testCases = int.Parse(Console.ReadLine());
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.
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!
