Sponsors

Codeforces Round #412 (rated, Div. 1, based on VK Cup 2017 Round 3), problem: (F) Test Data Generation, Accepted Solution In C/C++

#include<bits/stdc++.h>
#define ll long long

ll multmod(ll a, ll b, ll moder){
 a = (a % moder + moder) % moder, b = (b % moder + moder) % moder;
 ll ret = 0;
 for ( ; b; b >>= 1){
 if (b & 1){
 ret = ret + a >= moder ? ret + a - moder : ret + a;
 }
 a = a << 1 > moder ? (a << 1) - moder : a << 1;
 }
 return ret;
}

template <typename T> 
class modequa{
private:
 T remain, moder;
 
public:
 modequa <T>(){}
 modequa <T>(T remain, T moder) : remain(remain), moder(moder){}
 T getremain(){return remain;}
 T getmoder(){return moder;}
 
 void setvalue(T remain, T moder){
 this -> remain = remain;
 this -> moder = moder;
 }
 
 modequa <T> crt(const modequa <T> &p){
 T gcd = moder, x = 1, y = 0;
 for (T b = p.moder, x1 = 0, y1 = 1, r, s; b; ){
 r = x, s = y;
 x = x1, y = y1, x1 = r - x1 * (gcd / b), y1 = s - y1 * (gcd / b);
 r = gcd % b, gcd = b, b = r;
 }
 if ((p.remain - remain) % gcd) return modequa <T>(0, 0);
 T lcm = moder / gcd * p.moder;
 T ans = (p.remain - remain) / gcd;
 ans = multmod(multmod(ans, x, lcm), moder, lcm);
 ans += remain;
 ans += ans < 0 ? lcm : ans >= lcm ? -lcm : 0;
 return modequa <T>(ans, lcm);
 }
};

// Èç¹ûÄ£Êý²»ÊÇÖÊÊý£¬ÄÇô»ù±¾¾ÍÖ»ÄÜ×ö¼Ó¼õ³ËºÍÇóµ¼ÁËorz 
class poly{
private:
 int *a;
 int length, size;
 int moder, root, invroot;
 // ³£ÓõÄÁ½×éÄ£ÊýΪ ((119 << 23) + 1, 3, 332748118) ºÍ ((479 << 21) + 1, 3, 334845270)

 int powermod(int a, int exp, int moder)const &{
 int ret = 1;
 for ( ; exp; exp >>= 1){
 if (exp & 1){
 ret = 1ll * a * ret % moder;
 }
 a = 1ll * a * a % moder;
 }
 return ret;
 }
 
 void NTT(int *a, int length, int type, int moder, int root)const &{
 int len = -1;
 for (int x = length; x; ++ len, x >>= 1);
 for(int i = 1, j = 0; i < length - 1; ++ i){
 for(int s = length; j ^= s >>= 1, ~j & s; );
 if(i < j){
 std::swap(a[i], a[j]);
 }
 }
 for (int i = 1; i <= len; ++ i){
 int unit = powermod(root, moder - 1 >> i, moder);
 for (int j = 0; j < length; j += 1 << i){
 int w = 1;
 for (int k = j, szk = 1 << i - 1; k < j + szk; ++ k){
 int s = a[k], t = 1ll * w * a[k + szk] % moder;
 a[k] = s + t >= moder ? s + t - moder : s + t;
 a[k + szk] = s - t < 0 ? s - t + moder : s - t;
 w = 1ll * w * unit % moder;
 }
 }
 }
 if (type == 1) return;
 int inv = powermod(length, moder - 2, moder);
 for (int i = 0; i < length; ++ i){
 a[i] = 1ll * a[i] * inv % moder;
 }
 }
 
 void apply(int size){
 if (!size) return;
 a = new int [size]();
 this -> size = size;
 }
 
 void destroy(){
 if (!size) return;
 delete [] a;
 a = nullptr;
 }
 
 void resize(int size){
 if (!size) return;
 int *aux = a;
 a = new int [size]();
 memcpy(a, aux, sizeof(int) * (length + 1));
 if (this -> size) delete [] aux;
 this -> size = size;
 }

public:
 poly() : length(-1), moder(0), root(0), invroot(0){a = nullptr;}
 // Èç¹ûÄ£Êý·ÇNTTÖÊÊý root ºÍ invroot Ëæ±ãÉè¾ÍºÃÀ±~ 
 poly(int length, int moder, int root, int invroot):length(length), moder(moder), root(root), invroot(invroot){apply(length + 2 << 1);}
 poly(const poly &p):length(p.length), moder(p.moder), root(p.root), invroot(p.invroot){apply(p.size); memcpy(a, p.a, sizeof(int) * (p.length + 1));}
 poly(const poly &p, int length):length(length), moder(p.moder), root(p.root), invroot(p.invroot){apply(length + 2 << 1); memcpy(a, p.a, sizeof(int) * (std::min(length, p.length) + 1));}
 ~poly(){destroy();}
 void clear(){destroy(); length = -1, size = moder = root = invroot = 0;}
 int &operator [](int n){return a[n];}
 int getlength(){return length;}
 void setmoder(int moder, int root, int invroot){this -> moder = moder, this -> root = root, this -> invroot = invroot;}
 int getmoder(){return moder;}
 
 void setlength(int length){
 if (length >= size) resize(length + 2 << 1);
 if (length >= this -> length){
 this -> length = length;
 return;
 }
 memset(a + length + 1, 0, sizeof(int) * (this -> length - length));
 this -> length = length;
 }
 
 poly &operator = (const poly &p){
 destroy();
 apply(p.size);
 length = p.length;
 moder = p.moder;
 root = p.root;
 invroot = p.invroot;
 memcpy(a, p.a, sizeof(int) * (length + 1));
 return *this;
 }
 
 // Ï൱ÓÚ³ËÒÔ x ^ dis
 poly operator << (const int &dis)const &{
 poly ret(length + dis, moder, root, invroot);
 memcpy(ret.a + dis, a, sizeof(double) * (length + 1));
 return ret;
 }
 
 // Ï൱ÓÚ³ýÒÔ x ^ dis
 poly operator >> (const int &dis)const &{
 if (dis > length) return poly(-1, moder, root, invroot);
 poly ret(length - dis, moder, root, invroot);
 memcpy(ret.a, a + dis, sizeof(int) * (ret.length + 1));
 return ret;
 }
 
 int value(int x){
 int now = 1, ret = 0;
 for (int i = 0; i <= length; ++ i){
 ret = (ret + 1ll * a[i] * now) % moder;
 now = 1ll * now * x % moder;
 }
 return ret;
 }
 
 poly operator + (const poly &p)const &{
 if (!~length) return p;
 if (!~p.length) return *this;
 poly ret(*this, std::max(length, p.length));
 for (int i = 0; i <= p.length; ++ i){
 ret.a[i] += p.a[i];
 ret.a[i] -= ret.a[i] >= moder ? moder : 0;
 }
 for ( ; ~ret.length && !ret.a[ret.length]; -- ret.length)
 ;
 return ret;
 }
 
 poly operator - (const poly &p)const &{
 if (!~length) return p;
 if (!~p.length) return *this;
 poly ret(*this, std::max(length, p.length));
 for (int i = 0; i <= p.length; ++ i){
 ret.a[i] -= p.a[i];
 ret.a[i] += ret.a[i] < 0 ? moder : 0;
 }
 for ( ; ~ret.length && !ret.a[ret.length]; -- ret.length)
 ;
 return ret;
 }
 
 poly operator - ()const &{
 poly ret(length, moder, root, invroot);
 for (int i = 0; i <= length; ++ i){
 ret.a[i] = a[i] ? moder - a[i] : 0;
 }
 return ret;
 }
 /*&
 poly operator * (const poly &p)const &{
 if (!~length || !~p.length) return poly(-1, moder, root, invroot);
 int n = length + p.length;
 int lengthret = 1;
 for ( ; lengthret <= n; lengthret <<= 1)
 ;
 int *aux = new int [lengthret]();
 int *aux1 = new int [lengthret]();
 memcpy(aux, a, sizeof(int) * (length + 1));
 memcpy(aux1, p.a, sizeof(int) * (p.length + 1));
 NTT(aux, lengthret, 1, moder, root);
 NTT(aux1, lengthret, 1, moder, root);
 for (int i = 0; i < lengthret; ++ i){
 aux[i] = 1ll * aux[i] * aux1[i] % moder;
 }
 NTT(aux, lengthret, -1, moder, invroot);
 poly ret(n, moder, root, invroot);
 memcpy(ret.a, aux, sizeof(int) * (n + 1));
 delete [] aux;
 delete [] aux1;
 return ret;
 }*/
 
 ///*-------------------- ÕâÊÇÄ£Êý·ÇNTTÖÊÊýµÄÄ£°å£¬Çë°´ÐèÈ¡ÓÃ~ ------------------------------
 poly operator *(const poly &p)const &{
 const int multmoder[2] = {(119 << 23) + 1, (479 << 21) + 1};
 const int multroot[2] = {3, 3};
 const int multinvroot[2] = {332748118, 334845270};
 if (!~length || !~p.length) return poly(-1, moder, root, invroot);
 int n = length + p.length;
 int lengthret = 1;
 for ( ; lengthret <= n; lengthret <<= 1)
 ;
 int *aux = new int [lengthret]();
 int *aux1 = new int [lengthret]();
 int *aux2 = new int [lengthret]();
 memcpy(aux, a, sizeof(int) * (length + 1));
 memcpy(aux2, p.a, sizeof(int) * (p.length + 1));
 NTT(aux, lengthret, 1, multmoder[0], multroot[0]);
 NTT(aux2, lengthret, 1, multmoder[0], multroot[0]);
 for (int i = 0; i < lengthret; ++ i){
 aux[i] = 1ll * aux[i] * aux2[i] % multmoder[0];
 }
 NTT(aux, lengthret, -1, multmoder[0], multinvroot[0]);
 memcpy(aux1, a, sizeof(int) * (length + 1));
 memset(aux2, 0, sizeof(int) * lengthret);
 memcpy(aux2, p.a, sizeof(int) * (p.length + 1));
 NTT(aux1, lengthret, 1, multmoder[1], multroot[1]);
 NTT(aux2, lengthret, 1, multmoder[1], multroot[1]);
 for (int i = 0; i < lengthret; ++ i){
 aux1[i] = 1ll * aux1[i] * aux2[i] % multmoder[1];
 }
 NTT(aux1, lengthret, -1, multmoder[1], multinvroot[1]);
 poly ret(n, moder, root, invroot);
 for(int i = 0; i <= n; ++ i){
 modequa <ll> equa(aux[i], multmoder[0]), equb(aux1[i], multmoder[1]);
 ret.a[i] = equa.crt(equb).getremain() % moder;
 }
 delete [] aux;
 delete [] aux1;
 delete [] aux2;
 return ret;
 }
 //----------------------------------------------------------------------------------------*/
 
 poly operator * (const int &p)const &{
 int q = (p % moder + moder) % moder;
 if (!q) return poly(-1, moder, root, invroot);
 poly ret(length, moder, root, invroot);
 for (int i = 0; i <= length; ++ i){
 ret.a[i] = 1ll * a[i] * q % moder;
 }
 return ret;
 }
 
 friend poly operator * (const int &q, const poly &p){return p * q;}
 poly &operator += (const poly &p){*this = *this + p; return *this;}
 poly &operator -= (const poly &p){*this = *this - p; return *this;}
 poly &operator *= (const poly &p){*this = *this * p; return *this;}
 poly &operator *= (const int &p){*this = *this * p; return *this;}
};

const int N = 100;

int maxn, maxa, moder;
int q[N];

int main(){
 scanf("%d%d%d", &maxn, &maxa, &moder);
 if (maxa == 1){
 return printf("0\n"), 0;
 }
 int cnt = 0;
 for (maxa >>= 1; maxa; maxa >>= 1){
 q[cnt ++] = maxa;
 }
 std::reverse(q, q + cnt);
 int ans = 1;
 poly a(maxn, moder, 0, 0);
 poly b(maxn, moder, 0, 0);
 a[0] = 1;
 b[1] = 1;
 for (int i = 0; i < cnt - 1; ++ i){
 poly ret1(a);
 ret1 = (ret1 + b) * (q[i] & 1 ? b : a);
 if (q[i] & 1 ? b[0] : a[0]){
 ret1 -= b;
 }
 else{
 ret1 += a;
 }
 ret1.setlength(maxn);
 poly ret2(a);
 ret2 = (ret2 + b) * (q[i] & 1 ? a : b);
 if (q[i] & 1 ? a[0] : b[0]){
 ret2 -= a;
 }
 else{
 ret2 += b;
 }
 ret2.setlength(maxn);
 if (q[i + 1] & 1){
 a = ret1;
 for (int i = 1; i <= maxn; ++ i){
 b[i] = (ret2[i] + ret1[i - 1] + ret2[i - 1]) % moder;
 }
 }
 else{
 a = ret1;
 b = ret2;
 }
 for (int i = 1; i <= maxn; i += 2){
 ans = (ans + b[i]) % moder;
 }
 }
 return printf("%d\n", ans), 0;
}

Together, Power Plants and...

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the...

Regional Lenders Are Merging...

The Consolidation Wave: Why Regional Lenders Are Merging to...

Rush announce reunion tour...

Rush Announces Triumphant Reunion Tour Five Years After Neil...

Partnership turns soggy paddocks...

The Kidney of the Landscape: How Partnerships are Revitalizing...

More CEOs want Elon...

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying...

I did not expect...

I Did Not Expect This Midrange Sony Soundbar to...

Together, Power Plants and Greenhouses Can Feed Humanity.

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the quest for sustainable practices and improved global food security, engineers are increasingly looking toward solutions...

Regional Lenders Are Merging to Answer the Challenge From Megabanks

The Consolidation Wave: Why Regional Lenders Are Merging to Fight Megabank Dominance The landscape of American banking is undergoing a rapid transformation, characterized by a...

Rush announce reunion tour five years after the death of drummer Neil Peart

Rush Announces Triumphant Reunion Tour Five Years After Neil Peart’s Passing The landscape of progressive rock was irrevocably changed five years ago with the passing...

Partnership turns soggy paddocks into wetlands – and a model for cleaner waterways

The Kidney of the Landscape: How Partnerships are Revitalizing Waterways Through Wetland Creation Wetlands have long been dubbed the 'kidneys of the landscape,' and for...

More CEOs want Elon Musk–style ‘moonshot’ pay packages—but comp experts are raising alarms

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying Compensation Experts A new, highly ambitious trend is sweeping through corporate boardrooms: the demand for "moonshot"...

I did not expect this midrange Sony soundbar to rival my Sonos system like this

I Did Not Expect This Midrange Sony Soundbar to Rival My Sonos System Sony's Bravia Theater System 6, a mid-range soundbar, has surprisingly impressed reviewers...

Combination of coaching, personnel has LSU’s defense ‘playing great’

LSU's Defensive Surge: A Winning Combination of Coaching and Personnel The LSU Tigers' impressive defensive turnaround hasn't been a matter of luck; it's a strategic...

Disney’s Kimmel suspension shows Trump’s increasing grip over media

Disney’s Kimmel Suspension: Trump’s Tightening Grip on Media? The recent suspension of Jimmy Kimmel from Disney, following controversial comments about former President Trump, has sparked...

New breath sensor detects diabetes quickly and easily

New Breath Sensor Detects Diabetes Quickly and Easily Diabetes affects millions, often going undiagnosed until significant health problems arise. Traditional methods of diagnosis, such...