\(\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 [1] , a simple idea is to set each element of the matrix as a polynomial

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

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[50], 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 File=getFile(), n=read(9), K=read(9);
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)
        for(int j=1;j<=n;++j) f[i][j]=read(9);
    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\) ↩︎