304 North Cardinal St.
Dorchester Center, MA 02124

# Swarm of Polygons CodeChef Solution

## Swarm of Polygons CodeChef Solution in C++17

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

#define f1(i,n) for(int i=1; i<=n; ++i)
#define f0(i,n) for(int i=0; i<n; ++i)
#define fi first
#define se second

#define TP template
#define TN typename
#define el cerr << "\n";
TP<TN T> void pr1(T &x) {cerr << x;}
TP<TN H, TN T> void pr1(pair<H, T> &x) {
cerr << '{'; pr1(x.first);
cerr << ','; pr1(x.second); cerr << '}';
}
void pr() { el; }
TP<TN H, TN... T> void pr(H h, T... t) {
cerr << " "; pr1(h); pr(t...);
}
#define db(x...) {cerr << "[" << #x << "]:", pr(x);}
#define dbg(x) {cerr << "[" << #x << "]: {";\
for (auto &i : x) {cerr << " ", pr1(i);} cerr << " }\n";}

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp make_pair

const int MOD = 1e9 + 7;

int mul(int a, int b) {
return (ll)a * b % MOD;
}

int add(int a, int b) {
a += b; if (a >= MOD) a -= MOD; return a;
}

int n, k, a, b, c, m;
void input() {cin >> n >> k >> a >> b >> c >> m;}
const int N = 1e6 + 4;

vi tmp;
void mult(vi &a, vi &b) { // a *= b
tmp.assign(a.size(), 0);
for (int i = 0; i <= k; ++i) {
for (int r = 0; r <= i; ++r) {
tmp[i] = add(tmp[i], mul(a[r], b[i - r]));
}
}
copy(tmp.begin(), tmp.end(), a.begin());
}

int ar[N];

using vvi = vector<vector<int>>;
int doDp(int start, int len) {
/*
dp[i][j] = choose i points in first j sides

dp[0][j] = 1
*/

// for (int i = 1; i <= k; ++i) {
// 	for (int j = i; j <= n; ++j) {
// 		dp[i][j] = dp[i - 1][j - 1] * ar[j] + dp[i][j - 1];
// 	}
// }

/*
dp[i][j] = choose i points in first j sides of cycle

dp[0][j] = 1
*/
// db(start, len);

vvi dp(k + 1, vi(len + 1, 0));
for (int j = 0; j <= len; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
for (int j = i; j <= len; ++j) {
mul(dp[i - 1][j - 1], ar[start + j - 1]), dp[i][j - 1]
);
}
}

/*
f[i] = choose i points in all cycles

f[0][j] = 1

f[i][1] = dp[i][len]
*/
int segs = (n - start) / len;

vi f(k + 1, 0);
f[0] = 1;
vi A(k + 1);
for (int i = 0; i <= k; ++i) A[i] = dp[i][len];
// dbg(A);
// db(segs);

while (segs) {
if (segs % 2) mult(f, A);
mult(A, A);
segs /= 2;
}
// dbg(f);

/*
g[i][j] = choose i points in all cycles and j last sides

g[0][j] = 1

g[i][0] = f[i][segs]
*/
int tail = (n - start) % len;
// db(tail);
vvi g(k + 1, vi(tail + 1, 0));
for (int j = 0; j <= tail; ++j) {
g[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
g[i][0] = f[i];
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= tail; ++j) {
mul(g[i - 1][j - 1], ar[start + j - 1]), g[i][j - 1]
);
}
}

/*
h[i][j] = choose i points in all cycles, all last sides and j first sides

h[0][j] = 1

h[i][0] = g[i][tail]
*/
vvi h(k + 1, vi(start + 1, 0));
for (int j = 0; j <= start; ++j) {
h[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
h[i][0] = g[i][tail];
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= start; ++j) {
mul(h[i - 1][j - 1], ar[j - 1]), h[i][j - 1]
);
}
}

return h[k][start];
}

int first[N];
int solve() {
// db(n, k, a, b, c, m);
fill_n(first, m, -1);
ar[0] = a;
first[a] = 0;
int start = 0, len = m;
for (int i = 1; i < m; ++i) {
ar[i] = ((ll)b * ar[i - 1] + c) % m;
// db(i, ar[i]);
if (first[ar[i]] != -1) {
start = first[ar[i]];
len = i - start;
break;
}
first[ar[i]] = i;
}

// db(start, len);

return doDp(start, len);
// return -1;
}
void go() {
int t;
cin >> t;
while (t--) {
input();
cout << solve() << '\n';
}
}

signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin.exceptions(cin.failbit);

go();

return 0;
}``````

## Swarm of Polygons CodeChef Solution in C++14

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

#define f1(i,n) for(int i=1; i<=n; ++i)
#define f0(i,n) for(int i=0; i<n; ++i)
#define fi first
#define se second

#define TP template
#define TN typename
#define el cerr << "\n";
TP<TN T> void pr1(T &x) {cerr << x;}
TP<TN H, TN T> void pr1(pair<H, T> &x) {
cerr << '{'; pr1(x.first);
cerr << ','; pr1(x.second); cerr << '}';
}
void pr() { el; }
TP<TN H, TN... T> void pr(H h, T... t) {
cerr << " "; pr1(h); pr(t...);
}
#define db(x...) {cerr << "[" << #x << "]:", pr(x);}
#define dbg(x) {cerr << "[" << #x << "]: {";\
for (auto &i : x) {cerr << " ", pr1(i);} cerr << " }\n";}

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp make_pair

const int MOD = 1e9 + 7;

int mul(int a, int b) {
return (ll)a * b % MOD;
}

int add(int a, int b) {
a += b; if (a >= MOD) a -= MOD; return a;
}

int n, k, a, b, c, m;
void input() {cin >> n >> k >> a >> b >> c >> m;}
const int N = 1e6 + 4;

vi tmp;
void mult(vi &a, vi &b) { // a *= b
tmp.assign(a.size(), 0);
for (int i = 0; i <= k; ++i) {
for (int r = 0; r <= i; ++r) {
tmp[i] = add(tmp[i], mul(a[r], b[i - r]));
}
}
copy(tmp.begin(), tmp.end(), a.begin());
}

int ar[N];

using vvi = vector<vector<int>>;
int doDp(int start, int len) {
/*
dp[i][j] = choose i points in first j sides

dp[0][j] = 1
*/

// for (int i = 1; i <= k; ++i) {
// 	for (int j = i; j <= n; ++j) {
// 		dp[i][j] = dp[i - 1][j - 1] * ar[j] + dp[i][j - 1];
// 	}
// }

/*
dp[i][j] = choose i points in first j sides of cycle

dp[0][j] = 1
*/
// db(start, len);

vvi dp(k + 1, vi(len + 1, 0));
for (int j = 0; j <= len; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
for (int j = i; j <= len; ++j) {
mul(dp[i - 1][j - 1], ar[start + j - 1]), dp[i][j - 1]
);
}
}

/*
f[i] = choose i points in all cycles

f[0][j] = 1

f[i][1] = dp[i][len]
*/
int segs = (n - start) / len;

vi f(k + 1, 0);
f[0] = 1;
vi A(k + 1);
for (int i = 0; i <= k; ++i) A[i] = dp[i][len];
// dbg(A);
// db(segs);

while (segs) {
if (segs % 2) mult(f, A);
mult(A, A);
segs /= 2;
}
// dbg(f);

/*
g[i][j] = choose i points in all cycles and j last sides

g[0][j] = 1

g[i][0] = f[i][segs]
*/
int tail = (n - start) % len;
// db(tail);
vvi g(k + 1, vi(tail + 1, 0));
for (int j = 0; j <= tail; ++j) {
g[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
g[i][0] = f[i];
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= tail; ++j) {
mul(g[i - 1][j - 1], ar[start + j - 1]), g[i][j - 1]
);
}
}

/*
h[i][j] = choose i points in all cycles, all last sides and j first sides

h[0][j] = 1

h[i][0] = g[i][tail]
*/
vvi h(k + 1, vi(start + 1, 0));
for (int j = 0; j <= start; ++j) {
h[0][j] = 1;
}
for (int i = 1; i <= k; ++i) {
h[i][0] = g[i][tail];
}
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= start; ++j) {
mul(h[i - 1][j - 1], ar[j - 1]), h[i][j - 1]
);
}
}

return h[k][start];
}

int first[N];
int solve() {
// db(n, k, a, b, c, m);
fill_n(first, m, -1);
ar[0] = a;
first[a] = 0;
int start = 0, len = m;
for (int i = 1; i < m; ++i) {
ar[i] = ((ll)b * ar[i - 1] + c) % m;
// db(i, ar[i]);
if (first[ar[i]] != -1) {
start = first[ar[i]];
len = i - start;
break;
}
first[ar[i]] = i;
}

// db(start, len);

return doDp(start, len);
// return -1;
}
void go() {
int t;
cin >> t;
while (t--) {
input();
cout << solve() << '\n';
}
}

signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin.exceptions(cin.failbit);

go();

return 0;
}``````

## Swarm of Polygons CodeChef Solution in C

``````#include <stdio.h>

#include <string.h>

#define LL long long
#define md 1000000007
#define N 1010000
#define K 22
#define S(a) memset(a,0,sizeof(a))
#define _T for(i=0;i<=k;i++)

main()
{
int fall, n, k, xx, yy, zz, q, len, num, st, i, j, sr, res, x[N], y[N], was[N], f[K], g[K], a[K], b[K];
for(scanf("%d",&fall); fall--; printf("%d\n",res))
{
for(i=!scanf("%d %d %d %d %d %d",&n,&k,&xx,&yy,&zz,&q); i<q; was[i++]=-1);
for(st=n,x[(was[xx]=len=num=!(i=1))]=xx; i<n; was[x[i]]=i,i++)
if(was[(x[i]=((LL)x[i-1]*yy+zz)%q)]!=-1)
{
num=(n-i)/(len=i-was[x[i]])+1;
st=n-len*num;
break;
}
for(S(g),g[i=0]=1; i<st; i++)
for(j=k; j>0; g[j]=(g[j]+(LL)g[j-1]*x[i])%md,j--);
S(f);
f[0]=1;
if(len)
{
for(y[!(i=1)]=x[st]; i<len; y[i]=((LL)y[i-1]*yy+zz)%q,i++);
for(i=0; i<len; i++)
for(j=k; j>0; f[j]=(f[j]+(LL)f[j-1]*y[i])%md,j--);
}
for(S(a),a[0]=sr=1; (sr<<1)<=num; sr<<=1);
for(;sr; sr>>=1)
{
_T b[i]=0;
_T for(j=0; j<=k-i; j++)
b[i+j]=(b[i+j]+(LL)a[i]*a[j])%md;
_T a[i]=b[i];
if(num>=sr)
{
num-=sr;
_T b[i]=0;
_T for(j=0; j<=k-i; j++)
b[i+j]=(b[i+j]+(LL)a[i]*f[j])%md;
_T a[i]=b[i];
}
}
res=0;
_T res=(res+(LL)a[i]*g[k-i])%md;
}
return 0;
}``````

## Swarm of Polygons CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func main() {

var buf bytes.Buffer
for tc > 0 {
tc--
n, k, a, b, c, m := arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]
res := solve(n, k, a, b, c, m)
buf.WriteString(fmt.Sprintln(fmt.Sprintf("%d", res)))
}
fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func modAdd(a, b int, mod int) int {
a += b
if a >= mod {
a -= mod
}
return a
}

func modMul(a, b int, mod int) int {
r := int64(a) * int64(b)
return int(r % int64(mod))
}

func pow(a, b int, mod int) int {
r := 1
for b > 0 {
if b&1 == 1 {
r = modMul(r, a, mod)
}
a = modMul(a, a, mod)
b >>= 1
}
return r
}

const MOD = 1000000007

const MAX_L = 1 << 20

func solve(n, k, a, b, c, m int) int {
x := make([]int, MAX_L)
x[1] = a % m
vis := make([]int, MAX_L)
vis[a] = 1

var prefixLength, cycleLength int

for i := 2; true; i++ {
x[i] = int((int64(b)*int64(x[i-1]) + int64(c)) % int64(m))
if vis[x[i]] > 0 {
prefixLength = vis[x[i]] - 1
cycleLength = i - vis[x[i]]
break
}
vis[x[i]] = i
}

cycleCount := (n - prefixLength) / cycleLength
suffixLength := (n - prefixLength) % cycleLength

dp := make([]int, k+1)
dp[0] = 1
prefixDp := make([]int, k+1)
suffixDp := make([]int, k+1)
ndp := make([]int, k+1)
cycleDp := make([]int, k+1)
for i := 1; i <= prefixLength+cycleLength; i++ {
for j := k; j >= 1; j-- {
dp[j] = modAdd(dp[j], modMul(x[i], dp[j-1], MOD), MOD)
}
if i == prefixLength {
copy(prefixDp, dp)
clear(dp)
dp[0] = 1
}
if i == prefixLength+suffixLength {
copy(suffixDp, dp)
}
if i == n {
copy(ndp, dp)
break
}
}

if n < prefixLength {
return ndp[k]
}

copy(cycleDp, dp)

if prefixLength != 0 {
copy(dp, prefixDp)
} else {
clear(dp)
dp[0] = 1
}

mulDp := func(a []int, b []int) {
for i := k; i >= 1; i-- {
var s int
for j := 0; j <= i; j++ {
s = modAdd(s, modMul(b[j], a[i-j], MOD), MOD)
}
a[i] = s
}
}

for cycleCount > 0 {
if cycleCount&1 == 1 {
mulDp(dp, cycleDp)
}
mulDp(cycleDp, cycleDp)
cycleCount >>= 1
}

if suffixLength != 0 {
mulDp(dp, suffixDp)
}

return dp[k]
}

func clear(arr []int) {
for i := 0; i < len(arr); i++ {
arr[i] = 0
}
}``````
##### Swarm of Polygons CodeChef Solution Review:

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

Find on CodeChef

##### Conclusion:

I hope this Swarm of Polygons 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!