Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Swarm of Polygons CodeChef Solution
Problem -Swarm of Polygons 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.
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) {
dp[i][j] = add(
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) {
g[i][j] = add(
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) {
h[i][j] = add(
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) {
dp[i][j] = add(
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) {
g[i][j] = add(
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) {
h[i][j] = add(
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() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
arr := readNNums(reader, 6)
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
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
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.
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!
