# $$\cal T_2$$ 100 million

## Description

Give you a bipartite graph with \ (2n\) points, with or without edges between the two points (enter \ (− 1\) if there is no edge), and ask whether there is a perfect match with a multiple of \ (k\).

$$n,k\leq 100,-1\leq a_{i,j}<k$$.

## Solution

"Perfect match" is prompting us to determinant  , a simple idea is to set each element of the matrix as a polynomial

$M_{i,j} = \begin{cases} 0& f(i,j) = -1\\ x^{f(i,j)} & f(i,j) \not = -1 \end{cases}$

Then, for the determinant, pay attention to the circular convolution of \ (k\), and finally check whether the \ (0\) item has a value. However, the problem is that there are \ (-1\) coefficients in the process of finding determinants, which may be offset, so it is necessary to assign a random weight to each element.

However, this is \ (\mathcal O(n^4\log n) \) and cannot be passed at all. Therefore, optimization is considered. similar $$\text{[CF917D] Stranger Trees}$$ Unit root (matching cyclic convolution) can be used for interpolation to achieve \ (\mathcal O(n^4) \). However, for this problem of finding the sum of coefficients of multiple times of \ (k\), unit root inversion can be considered

\begin{align}\text{Ans}&=\sum_{p}(-1)^{\sigma(p)}\cdot \left(\prod_{j=1}^n M_{j,p(j)}\right)\cdot [k\mid S]\\&=\sum_p(-1)^{\sigma(p)}\cdot \left(\prod_{j=1}^n M_{j,p(j)}\right)\cdot \left(\frac{1}{k}\cdot \sum_{j=0}^{k-1}\omega_{k}^{jS}\right)\\&=\frac{1}{k}\cdot \sum_{j=0}^{k-1}\sum_{p}(-1)^{\sigma(p)}\cdot \left(\prod_{q=1}^nM_{q,p(q)}\right)\cdot \omega_{k}^{jS}\\&=\frac{1}{k}\cdot \sum_{j=0}^{k-1}\sum_{p}(-1)^{\sigma(p)}\cdot \left(\prod_{q=1}^nM_{q,p(q)}\right)\cdot \left(\prod_{q=1}^n \omega_{k}^{j\cdot f(q,p(q))}\right)\\&=\frac{1}{k}\cdot \sum_{j=0}^{k-1}\sum_{p}(-1)^{\sigma(p)}\cdot \left(\prod_{q=1}^nM_{q,p(q)}\cdot \omega_{k}^{j\cdot f(q,p(q))\bmod k}\right)\end{align}

The complexity is still \ (\mathcal O(n^4) \), but the code is much less difficult (.

For the solution of unit root, find the prime number \ (p\) satisfying \ (k\mid \varphi(p) \) for each \ (k\), and then find the original root whose \ (g\) is \ (p\).

## Code

When typing the original root table, I forgot to call the linear screen every day, but there was \ (\text{70 pts}\) in it, which was adjusted for \ (114514\) years.

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ, w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}

# include <ctime>
# include <random>
# include <iostream>
using namespace std;

const int maxn = 105;
const int M[] = {
0, 998244853, 998244853, 998244853, 998244853, 998244911, 998244853, 998244899,
998244889, 998244991, 998244911, 998244853, 998244853, 998244911, 998244899, 998244991,
998245153, 998245169, 998244991, 998244991, 998245141, 998245207, 998244853, 998244943,
998244889, 998246101, 998244911, 998245189, 998245109, 998245483, 998244991, 998244889,
998245153, 998244853, 998245169, 998245571, 998245153, 998245349, 998244991, 998245483,
998245481, 998245697, 998245207, 998247323, 998244853, 998244991, 998244943, 998246537,
998245153, 998245543, 998246101, 998245543, 998245613, 998245037, 998245189, 998245711,
998245697, 998244991, 998245483, 998246371, 998245141, 998245481, 998244889, 998245207,
998245697, 998244911, 998244853, 998245463, 998245169, 998244943, 998245571, 998245091,
998245153, 998247553, 998245349, 998246101, 998246701, 998245403, 998245483, 998245739,
998246401, 998248213, 998245697, 998245483, 998245837, 998246461, 998247323, 998245483,
998245777, 998246251, 998244991, 998245613, 998245909, 998244889, 998246537, 998244991,
998245153, 998246401, 998245543, 998245711, 998246101
};
const int G[] = {
0, 1, 998244852, 5074615, 329616108, 512917536, 5074616, 284946685,
778179908, 40688012, 688466749, 272550417, 201706028, 213728379, 217683281, 382768647,
131656641, 622090284, 84307224, 522511112, 984467961, 572345760, 469839584, 559749723,
960906257, 391474713, 120711819, 628911619, 41844055, 369886176, 583814719, 996639691,
489964959, 851930040, 774005272, 389987180, 438125926, 554869056, 722022053, 316886605,
188836165, 197218309, 85719001, 792442674, 163382638, 722023357, 147367773, 648068025,
952629146, 241980780, 421356778, 102132604, 479526832, 22553849, 937814972, 358653419,
440955809, 401158213, 623549242, 479991815, 660231564, 604930244, 358184273, 629450949,
354165161, 965774360, 398185037, 487018917, 321035413, 356274137, 409115192, 423197538,
563825846, 91584998, 181825537, 793662250, 494698896, 71618210, 527847884, 375777121,
919487911, 878988347, 868346131, 195667810, 143694432, 847292750, 974305740, 793990151,
115107639, 324111322, 625131606, 992985137, 499918120, 327632765, 186023662, 717664166,
213999155, 244067369, 365832161, 178332126, 487905538,
};

int getFile() {
freopen("sort.in","r",stdin);
return true;
}

int a[maxn][maxn], _M[maxn][maxn], f[maxn][maxn];

const int mod = M[K], g = G[K];

int inv(int x,int y=mod-2,int r=1) {
for(; y; y>>=1, x=1ll*x*x%mod)
if(y&1) r=1ll*r*x%mod; return r;
}
int dec(int x,int y) { return x-y<0?x-y+mod:x-y; }
int inc(int x,int y) { return x+y>=mod?x+y-mod:x+y; }

int det() {
int j, tmp, Inv, ret=1; bool f=0;
for(int i=1;i<=n;++i) {
for(j=i; !a[j][i] && j<=n; ++j);
if(j>n) return 0;
if(i^j) swap(a[i],a[j]), f^=1;
Inv = inv(a[i][i]);
ret = 1ll*ret*a[i][i]%mod;
for(j=i+1;j<=n;++j) if(a[j][i]) {
tmp = 1ll*Inv*a[j][i]%mod;
for(int k=i;k<=n;++k)
a[j][k] = dec(a[j][k],1ll*tmp*a[i][k]%mod);
}
} return f? mod-ret: ret;
}

int main() {
freopen("sort.out","w",stdout);
for(int i=1;i<=n;++i)
mt19937 SEED(time(0)); int ans=0;
uniform_int_distribution <int> gen(1,1e9);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
if(~f[i][j]) _M[i][j] = gen(SEED);
for(int k=0;k<K;++k) {
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
if(f[i][j]==-1) a[i][j]=0;
else a[i][j] = 1ll*_M[i][j]*inv(g,1ll*k*f[i][j]%K)%mod;
ans = inc(ans,det());
} puts(ans? "Yes": "No");
return 0;
}


# $$\cal T_3$$ 100 million fields

## Description

Maintain a sequence \ (\{a\}\) with a length of \ (n\). Given the initial value, there are \ (m\) queries. Three operations need to be supported:

• 1 l r x, bitwise the \ (a_i\) of \ (i\in[l,r]\) and the upper \ (x\);
• 2 l r x, place \ (a_i\) of \ (i\in[l,r]\) or up \ (x\);
• 3 l r, ask the maximum value of \ (a_i\) of \ (i\in[l,r]\).

$$n,m\leq 2\cdot 10^5,a_i,x<2^{20}$$.

## Solution

Why never will there be a potential energy segment tree hello?

Explain the practice first, then analyze the complexity. Maintain bitwise and, bitwise OR, maximum value and \ (\rm tag\) for each node of the segment tree. Taking bitwise or modifying \ ((l,r,x) \) as an example, considering the binary \ (k\) bit, first of all, it has no effect that the \ (k\) bit of \ (x\) is zero. If all the numbers in the interval are zero in this bit and the \ (k\) bit of \ (x\) is \ (1\), then this operation becomes interval addition, and we include the value of interval addition in \ (\rm tag\); On the contrary, if there is a number with \ (1\) in this bit, it cannot be added directly to the interval. First, the tag is passed down, and then the sub interval is recursively passed.

Set potential energy function \ (\Phi(o)=\sum_{i=0}^{\log V}f(o,i) \), where \ (f(o,i) \) indicates that the \ (i\) bits of all the numbers in the interval represented by node \ (o\) are not all equal (that is, $\rm bool$expression), then:

• For each modification, similar to the idea of \ (\rm zkw\) line segment tree, go up from the leaf node represented by \ (l-1,r+1\). When you go to \ (p\) and meet two sons, one belongs to the modification interval and the other does not belong to the modification interval, this modification makes \ (p\) increase the potential energy of \ (\ log V\) at most. Since the level of \ (p\) is \ (\log n\), you can modify \ (\Delta\Phi=\log n\log V\) at a time, Increase the potential energy of \ (q\log n\log V\) for all modifications;
• Mark downward transmission has no effect on potential energy;
• The modified interval is divided into \ (\log n\) segments on the segment tree. When a node recurses downward, its potential energy is reduced by at least \ (1\) and at most \ (\log V\)

The initial potential energy of the interval is \ (n\log n\log V\), so the total complexity is \ (\mathcal O((n+q)\cdot \log n\log V) \)

## Code

Believe in yourself.

1. It's really numb. I didn't think of the determinant at all. I'm \ (\rm joker\) ↩︎

Tags: linear algebra

Posted by rgriffin3838 on Thu, 02 Jun 2022 10:53:31 +0530