[preface]
HDU had a good experience in the first game. Except that the penalty time of 1007 was much more true, and the KD tree of 1002 was not written, everything else was OK and there was no pain mask.
Finally rk42, school 2 / 9
1001. Mod, Or and Everything
[title]
Given a positive integer
n
n
n. Beg
(
n
mod
1
)
or
(
n
mod
2
)
or
⋯
or
(
n
mod
n
)
(n\text{ mod }1)\text{ or }(n\text{ mod }2)\text{ or } \cdots \text{ or }(n\text{ mod }n)
(n mod 1) or (n mod 2) or ⋯ or (n mod n)
n
≤
1
0
12
n\leq 10^{12}
n≤1012，
T
≤
5000
T\leq 5000
T≤5000
[ideas]
This kind of question is very regular at first sight. Just type the table to find the law. You will probably find that the answer is 2 k − 1 2^k-1 2k − 1
Complexity O ( T log n ) O(T\log n) O(Tlogn)
[reference code]
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a),i##ss=(b);i<=i##ss;i++)
#define dwn(i,a,b) for(int i=(a),i##ss=(b);i>=i##ss;i--)
#define deb(x) cerr<<(#x)<<":"<<(x)<<'\n'
#define pb push_back
#define fi first
#define se second
#define hvie '\n'
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
int yh(){
int ret=0;bool f=0;char c=getchar();
while(!isdigit(c)){if(c==EOF)return -1;if(c=='-')f=1;c=getchar();}
while(isdigit(c))ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
return f?-ret:ret;
}
const int maxn=3e5+5;
signed main(){
vector<pii> val;
int now=2,cur=2,sum=0;
val.pb({2,0});
rep(i,1,62){
cur+=now;
sum=(1ll<<i)-1;
val.pb({cur,sum});
now<<=1;
// cout<<cur<<" "<<sum<<hvie;
}
dwn(_,yh(),1){
int n=yh();
auto it=lower_bound(val.begin(),val.end(),(pii){n,0ll});
// it--;
cout<<it->se<<hvie;
}
return 0;
}
1002. Rocket land
[title]
x O y xOy On the xOy plane n n n rockets with weight are launched in numbered order, Q i i i rockets with radius of r i r_i The sum of the weights of all launched rockets within the circle of ri.
n ≤ 2 × 1 0 5 n\leq 2\times 10^5 n≤2 × 105, random data
[ideas]
When you see that the data is random and it is a plane weight and problem, just go directly to the KD tree.
Offline tree building can be done without reconstruction. It is mainly necessary to determine whether the rectangle is completely covered or separated.
Complexity O ( n n ) O(n\sqrt n) O(nn )
[reference code]
#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=5e5+10,K=2,mod=1e9+7,inf=0x3f3f3f3f;
int n,r[N],pos[N];
int read()
{
int ret=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')f=0;c=getchar();}
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return f?ret:-ret;
}
int now=0;
struct Point
{
int d[K],val,id;
friend bool operator < (const Point&A,const Point&B)
{
return A.d[now]<B.d[now];
}
}p[N],a[N];
void gmin(int &x,int y){x=min(x,y);}
void gmax(int &x,int y){x=max(x,y);}
ll sqr(ll x){return x*x;}
struct KDT
{
#define ls t[x].lc
#define rs t[x].rc
int sz,rt;
struct node
{
ll sum;
int mi[K],mx[K],lc,rc,exist,siz,fa;
Point p;
}t[N<<2];
void up(int x)
{
for(int i=0;i<K;++i)
{
t[x].mi[i]=t[x].mx[i]=t[x].p.d[i];
if(ls)
{
gmin(t[x].mi[i],t[ls].mi[i]);
gmax(t[x].mx[i],t[ls].mx[i]);
}
if(rs)
{
gmin(t[x].mi[i],t[rs].mi[i]);
gmax(t[x].mx[i],t[rs].mx[i]);
}
}
if(ls) t[ls].fa=x;
if(rs) t[rs].fa=x;
}
void pushup(int x)
{
t[x].sum=t[x].p.val*t[x].exist;
t[x].siz=t[x].exist;
if(ls) t[x].sum+=t[ls].sum,t[x].siz+=t[ls].siz;
if(rs) t[x].sum+=t[rs].sum,t[x].siz+=t[rs].siz;
}
void clean_point(int x)
{
t[x].sum=t[x].exist=0;t[x].siz=0;
ls=rs=0;t[x].fa=0;
}
void build(int &x,int l,int r,int D)
{
if(l>r)
{
x=0;
return;
}
x=++sz;clean_point(x);now=D;
int mid=(l+r)>>1;
nth_element(a+l,a+mid,a+r+1);
t[x].p=a[mid];pos[a[mid].id]=x;
build(ls,l,mid-1,D^1);
build(rs,mid+1,r,D^1);
up(x);
}
bool inside(int xc,int yc,int r,int xa,int ya,int xb,int yb)//left down && right up
{
ll tmp=sqr(r);
return (sqr(xa-xc)+sqr(ya-yc)<=tmp) && (sqr(xa-xc)+sqr(yb-yc)<=tmp) &&
(sqr(xb-xc)+sqr(ya-yc)<=tmp) && (sqr(xb-xc)+sqr(yb-yc)<=tmp);
}
bool outside(int xc,int yc,int r,int xa,int ya,int xb,int yb)
{
int tx,ty;
if(xa<=xc && xc<=xb) tx=xc;
else
{
if(xa>=xc) tx=xa;
else tx=xb;
}
if(ya<=yc && yc<=yb) ty=yc;
else
{
if(ya>=yc) ty=ya;
else ty=yb;
}
return (sqr(tx-xc)+sqr(ty-yc)>sqr(r));
}
ll query(int x,int xc,int yc,int r)
{
if(!x || !t[x].siz) return 0;
if(inside(xc,yc,r,t[x].mi[0],t[x].mi[1],t[x].mx[0],t[x].mx[1])) return t[x].sum;
if(outside(xc,yc,r,t[x].mi[0],t[x].mi[1],t[x].mx[0],t[x].mx[1])) return 0;
return query(ls,xc,yc,r)+query(rs,xc,yc,r)+
inside(xc,yc,r,t[x].p.d[0],t[x].p.d[1],t[x].p.d[0],t[x].p.d[1])*t[x].p.val*t[x].exist;
}
void update(int x)
{
x=pos[x];t[x].exist=1;
while(x) pushup(x),x=t[x].fa;
}
void clear()
{
sz=rt=0;
}
#undef ls
#undef rs
}T;
int main()
{
//freopen("1.in","r",stdin);
//freopen("a.out","w",stdout);
for(int TT=read();TT--;)
{
n=read();T.clear();
for(int i=1;i<=n;++i) p[i].d[0]=read(),p[i].d[1]=read(),p[i].val=read(),p[i].id=i,r[i]=read(),a[i]=p[i];
T.build(T.rt,1,n,0);
for(int i=1;i<=n;++i)
{
T.update(i);
ll ans=T.query(T.rt,p[i].d[0],p[i].d[1],r[i]);
printf("%lld\n",ans);
}
}
}
1003. Puzzle loop
[title]
n + 1 n+1 n+1 horizontal lines and m + 1 m+1 m+1 vertical lines form a n × m n\times m n × m grid, now color some edges of the grid so that the number of times the four edges constituting a grid are painted is odd or even (or unlimited). At the same time, the painted edges are required to form several closed graphics, and there are no painted edges inside each closed graphics. Ask about the number of feasible schemes
n , m ≤ 17 n,m\leq 17 n,m≤17
[ideas]
First of all, an important observation is that there are no edges inside a closed graph. For a closed graph, we can equivalently see that each small square of the graph paints four edges (which can be repeated), which will not change the parity.
Then, the problem is equivalent to considering whether each small square is painted on all four sides independently, which looks like a contour line DP. Then, when the team-mates wrote half of the game, they found that they couldn't do it, so they didn't do it.
But after thinking for a while, I gave a more correct solution. (the list seems to be skewed. Not many people have passed this question)
In fact, the color parity of each square edge is related to whether its adjacent four edges are painted or not. This is an XOR equation system. What we require is the number of solutions of the XOR equation system, that is, the number of free elements k k k. The answer is 2 k 2^k 2k, of course, there is no solution.
Complexity O ( n 6 ) O(n^6) O(n6), but solving the XOR equation runs fast. You can even bitset it.
[reference code]
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),i##ss=(b);i<=i##ss;i++)
#define dwn(i,a,b) for(int i=(a),i##ss=(b);i>=i##ss;i--)
#define deb(x) cerr<<(#x)<<":"<<(x)<<'\n'
#define pb push_back
#define fi first
#define se second
#define hvie '\n'
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
int yh(){
int ret=0;bool f=0;char c=getchar();
while(!isdigit(c)){if(c==EOF)return -1;if(c=='-')f=1;c=getchar();}
while(isdigit(c))ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
return f?-ret:ret;
}
const int maxn=3e5+5;
int A[350][350];
int m,n;
int xor_guass(int m, int n) //A is the return rank of the coefficient matrix of XOR equations
{
int i = 0, j = 0, k, r, u;
while(i < m && j < n){//Currently working on equation i, variable j
r = i;
for(int k = i; k < m; k++) if(A[k][j]){r = k; break;}
if(A[r][j]){
if(r != i) for(k = 0; k <= n; k++) swap(A[r][k], A[i][k]);
//After elimination, the first non-zero column in row i is column j, and column j in row U > i is all 0
for(u = i + 1; u < m; u++) if(A[u][j])
for(k = i; k <= n; k++) A[u][k] ^= A[i][k];
i++;
}
j++;
}
// rep(i,0,m-1){
// rep(j,0,n-1)
// }
dwn(i,m-1,0){
bool all0=1;
rep(j,0,n-1) if(A[i][j]) {
all0=0;break;
}
if(all0&&A[i][n]){
return 0x3f3f3f3f;
}
}
// cout<<i<<hvie;
return i;
}
int id[18][18],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
ll ksm(ll x,ll p,ll mod){
ll ans=1;
for(;p;p>>=1,x=x*x%mod) if(p&1) ans=ans*x%mod;
return ans;
}
int main(){
dwn(_,yh(),1){
m=yh()-1,n=yh()-1;
rep(i,0,m-1)rep(j,0,n-1) id[i][j]=i*n+j;
int row=0;
// memset(A,0,sizeof(A));
rep(i,0,m-1)rep(j,0,n-1){
char c=getchar();while(!isdigit(c)&&c!='.')c=getchar();
rep(k,0,m*n) A[row][k]=0;
if(isdigit(c)){
rep(k,0,3){
int i_=i+dx[k];
int j_=j+dy[k];
if(i_>=0&&j_>=0&&i_<m&&j_<n){
A[row][id[i_][j_]]=1;
}
}
// A[row][id[i][j]]=1;
A[row][m*n]=(int)(c-'0');
row++;
}
}
int rk=xor_guass(row,m*n);
if(rk==0x3f3f3f3f){
puts("0");
}
else cout<<ksm(2,(n*m-rk),998244353)<<hvie;
}
return 0;
}
1004. Another thief in a Shop
[title]
There are in the shop n n n items, No i i What is the value of type i a i a_i ai, each can be taken infinitely. How many ways can the total value be obtained k k k. The answer is to modulo a common prime.
n ≤ 100 , a i ≤ 10 , k ≤ 1 0 18 n\leq 100,a_i\leq 10,k\leq 10^{18} n≤100,ai≤10,k≤1018
[ideas]
First of all, Naive's idea is that each scheme is actually in the form of a generating function, that is 1 1 − x a i \frac 1 {1-x^{a_i}} 1 − xai 1, the answer is to ask for this n n The second of the product of n generating functions k k k-term coefficient.
But that doesn't seem to work.
Generally speaking, this kind of thing must be interpolated, but I haven't thought of it for a long time. My mathematical skills are not very good.
Initial setting
f
[
0
]
=
1
f[0]=1
f[0]=1 for each
a
[
i
]
a[i]
a[i], with the following transfer formula
f
[
j
]
=
f
[
j
−
a
[
i
]
]
f[j]=f[j-a[i]]
f[j]=f[j−a[i]]
So we come to a conclusion
O
(
n
k
)
O(nk)
DP of O(nk)
If converted to mathematical form, make
f
(
i
,
j
)
f(i,j)
f(i,j) means only the front
j
j
Function value of j items, then:
f
(
i
,
j
)
=
∑
i
=
0
⌊
i
a
j
⌋
f
(
i
−
a
j
,
j
−
1
)
f(i,j)=\sum_{i=0}^{\lfloor \frac{i}{a_j} \rfloor}f(i-a_j,j-1)
f(i,j)=i=0∑⌊aji⌋f(i−aj,j−1)
Finally, we will find the answer
f
(
k
,
n
)
f(k,n)
All of f(k,n)
∑
\sum
The values above the Σ symbol are
k
a
j
\frac {k}{a_j}
aj k, so if we're right
k
k
k-mode
a
[
i
]
a[i]
By classifying the remainder of a[i], we can get a summation without integer division symbol.
because
a
[
i
]
≤
10
a[i]\leq 10
a[i] ≤ 10, we only need to consider
k
k
k-mode
lcm
(
a
[
i
]
)
\text{lcm}(a[i])
The remainder of lcm(a[i]) (lcm no more than 2520), the answer will become a
k
lcm
\frac {k} {\text{lcm}}
lcmk related
n
n
n-degree integer coefficient polynomial, and then you can interpolate.
Complexity O ( n 2 ⋅ lcm ) O(n^2\cdot \text{lcm}) O(n2⋅lcm)
#include<bits/stdc++.h>
using namespace std;
#define N 6000010
#define LL long long
#define MOD 1000000007
int T,n,a[110],f[N];
LL k,y[110],pre[110],suf[110],inv[110];
LL Lagrange(LL x)
{
LL res=0;
pre[0]=suf[n+1]=1;
for(int i=1;i<=n;i++)
pre[i]=1ll*pre[i-1]*((x-i)%MOD)%MOD;
for(int i=n;i>=1;i--)
suf[i]=1ll*suf[i+1]*((x-i)%MOD)%MOD;
for(int i=1;i<=n;i++)
{
int l=1ll*pre[i-1]*suf[i+1]%MOD*inv[n-i]%MOD*inv[i-1]%MOD;
l=1ll*l*y[i]%MOD;
if((n^i)&1)l=MOD-l;
res=(res+l)%MOD;
}
return res;
}
int main()
{
inv[0]=inv[1]=f[0]=1;
for(LL i=2;i<110;i++)inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
for(LL i=2;i<110;i++)inv[i]=inv[i]*inv[i-1]%MOD;
scanf("%d",&T);
while(T--){
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int lcm=a[1];
for(int i=2;i<=n;i++){
int d=__gcd(lcm,a[i]);
lcm=lcm*a[i]/d;
}
for(int i=1;i<=n*lcm;i++)f[i]=0;
for(int j=1;j<=n;j++){
for(int i=a[j];i<=n*lcm;i++){
f[i]=(f[i]+f[i-a[j]])%MOD;
}
}
if(k<=n*lcm){
printf("%d\n",f[k]);
continue;
}
for(int i=k%lcm;i<n*lcm;i+=lcm)y[i/lcm+1]=f[i];
printf("%lld\n",Lagrange(k/lcm+1));
}
}
1005. Minimum Spanning Tree
[title]
n − 1 n-1 n − 1 point number 2 2 2 to n n n. The edge weights between two points are numbered lcm \text{lcm} lcm, find the minimum spanning tree weight.
n ≤ 1 0 7 n\leq 10^7 n ≤ 107, multiple groups of data
[ideas]
Considering the construction of minimum spanning tree, we only need to find a minimum connection for each number (it must not be excellent in the future).
Obviously, prime numbers must sum 2 2 2 is connected, otherwise the weight will be increased
A non prime number can be connected to one of its factors, and the answer is itself.
Just count the two parts separately.
Complexity O ( n + T ) O(n+T) O(n+T)
[reference code]
#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=1e7+1,M=22,mod=1e9+7,inf=0x3f3f3f3f;
bool notpri[N];
int pri[1000000],cnt;
ll sum[N];
int read()
{
int ret=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')f=0;c=getchar();}
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return f?ret:-ret;
}
void init()
{
notpri[1]=1;
for(int i=2;i<N;++i)
{
if(!notpri[i]) pri[++cnt]=i;
for(int j=1;j<=cnt;++j)
{
ll t=1ll*i*pri[j];
if(t>=N) break;
notpri[t]=1;
if(!(i%pri[j])) break;
}
}
for(int i=2;i<N;++i) sum[i]=sum[i-1]+(notpri[i]^1)*i;
}
signed main()
{
init();
for(int T=read();T--;)
{
ll n=read();
ll tmp=1ll*n*(n+1)/2-1-sum[n];
ll ans=max(0ll,(sum[n]-2))*2+tmp;
printf("%lld\n",ans);
}
return 0;
}
1006. Xor Sum
[title]
Given a length of n n Sequence of n a i a_i ai, find the shortest continuous sequence so that the XOR sum is greater than or equal to k k k
n ≤ 1 0 5 , k , a i < 2 30 n\leq 10^5,k,a_i<2^{30} n≤105,k,ai<230
[ideas]
Classic XOR and questions.
First, make a prefix XOR sum. The problem is to find the nearest two points so that the sum of two points is greater than or equal to k k k.
In fact, each point on Trie is also a range interval, satisfying XOR and greater than or equal k k The point of k can be expressed as continuous log \log log interval, also on Trie log \log log points. Then, for this thing, we only need to record the rightmost point on each point of the Trie tree, then enumerate the right endpoint of the sequence and run all the points on the Trie tree ≥ k \geq k ≥ k, and insert the right endpoint.
Complexity O ( n log a i ) O(n\log a_i) O(nlogai)
The game was stupid, set a two-point rightmost position, and the problem became whether there was a point so that the XOR sum was greater than or equal to k k k. Force complexity into O ( n log n log a i ) O(n\log n\log a_i) O(nlognlogai), but it can also pass.
[reference code]
#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=1e5+5,mod=1e9+7,inf=0x3f3f3f3f;
int n,K;
int a[N];
int read()
{
int ret=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')f=0;c=getchar();}
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return f?ret:-ret;
}
struct Trie
{
const int M=30;
int id[N*30][2],mx[N*30][2],ed[N*30],cnt,rt;
void clear()
{
for(int i=0;i<=cnt;++i) id[i][0]=id[i][1]=0,mx[i][0]=mx[i][1]=-1,ed[i]=0;
//memset(id,0,sizeof(id));
//memset(mx,-1,sizeof(mx));
cnt=rt=1;
}
void insert(int x,int d)
{
int now=rt;
for(int i=M-1;i>=0;--i)
{
int t=(x>>i)&1;
if(!id[now][t]) id[now][t]=++cnt;
mx[now][t]=max(mx[now][t],d);now=id[now][t];
//printf("in [%d][%d]\n",i,t);
}
ed[now]=max(ed[now],d);
//printf("insert:%d %d %d %d\n",x,d,now,ed[now]);
}
int find(int x,int k)
{
//printf("nowfind:%d %d\n",x,k);
int now=rt;
for(int i=M-1;i>=0;--i)
{
int t=(x>>i)&1;
// printf("mine:%d checkmx:%d\n",t,mx[now][t^1]);
if(!id[now][t^1] || mx[now][t^1]<k)
{
//if(!id[i][t]) return -1;
//printf("go:%d %d\n",i,t);
now=id[now][t];
}
else
{
// printf("go:%d %d\n",i,t^1);
now=id[now][t^1];
}
}
if(ed[now]>=k)
{
// printf("get:%d %d\n",now,ed[now]);
return ed[now];
}
else return -1;
}
}tr;
signed main()
{
for(int T=read();T--;)
{
n=read();K=read();
for(int i=1;i<=n;++i) a[i]=read()^a[i-1];
//puts("");
if(K==0)
{
puts("1 1");
continue;
}
int fg=0;
for(int i=1;i<=n;++i)
if((a[i]^a[i-1])>=K)
{
printf("%d %d\n",i,i);
fg=1;
break;
}
if(fg) continue;
tr.clear();
tr.insert(0,0);
int ansl=-1,ansr=n+1;
for(int i=1;i<=n;++i)
{
tr.insert(a[i],i);
int l=0,r=i-1,ret=-1;
while(l<=r)
{
int mid=(l+r)>>1;
//printf("nowfind:%d %d %d\n",mid,i,a[i]);
int gt=tr.find(a[i],mid);
//printf("find:%d %d %d\n",gt,mid,i);
if(gt==-1 || (a[i]^a[gt])<K) r=mid-1;
else l=mid+1,ret=mid;
}
if(ret!=-1)
{
if(i-ret<ansr-ansl+1)
ansl=ret+1,ansr=i;
}
// tr.insert(a[i],i);
//puts("");
}
if(ansr>n) puts("-1");
else printf("%d %d\n",ansl,ansr);
}
return 0;
}
/*
2
3 2
1 2 2
9 7
3 1 3 2 4 0 3 5 1
*/
1007. Pass!
[title]
have n n n people are passing the ball, and the initial position is 1 1 1. It is known to return after passing the ball several times 1 1 The value of digital analog 998244353 of scheme 1 is x x x. Find the minimum number of passes that meet the conditions.
n ≤ 1 0 6 , x ≤ 992344353 n\leq 10^6,x\leq 992344353 n ≤ 106,x ≤ 992344353, multiple groups of data
[ideas]
First, we can write an obvious recursive formula: let
f
[
i
]
[
0
/
1
]
f[i][0/1]
f[i][0/1] indicates transmission
i
i
After i times, the number of schemes in which the ball is not in 1, then:
f
[
i
]
[
0
]
=
f
[
i
−
1
]
[
0
]
⋅
(
n
−
2
)
+
f
[
i
−
1
]
[
1
]
f
[
i
]
[
1
]
=
f
[
i
−
1
]
[
0
]
⋅
(
n
−
2
)
f[i][0]=f[i-1][0]\cdot (n-2)+f[i-1][1]\\ f[i][1]=f[i-1][0]\cdot(n-2)
f[i][0]=f[i−1][0]⋅(n−2)+f[i−1][1]f[i][1]=f[i−1][0]⋅(n−2)
Then it is found that the two can be merged and set
f
[
i
]
f[i]
f[i] is the biography
i
i
The scheme i is in 1. After sorting, we can get:
f
[
i
]
=
(
n
−
2
)
⋅
f
[
i
−
1
]
+
(
n
−
1
)
⋅
f
[
i
−
2
]
f[i]=(n-2)\cdot f[i-1]+(n-1)\cdot f[i-2]
f[i]=(n−2)⋅f[i−1]+(n−1)⋅f[i−2]
n
n
If n is a constant, then this is a linear recursive form. We can use the eigenvalue equation to find its general term formula:
f
[
t
]
=
1
n
⋅
(
(
n
−
1
)
t
+
(
n
−
1
)
⋅
(
−
1
)
t
)
f[t]=\frac 1 n\cdot((n-1)^t+(n-1)\cdot(-1)^t)
f[t]=n1⋅((n−1)t+(n−1)⋅(−1)t)
If the odd and even terms are considered separately, the problem is actually transformed into
a
b
≡
x
(
mod
998244353
)
a^b\equiv x(\text{mod } 998244353)
Minimum of ab ≡ x(mod 998244353)
b
b
b. This can be done with BSGS.
Complexity O ( p ) O(\sqrt{p}) O(p )
[reference code]
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int p = 998244353;
int ksm(int a, int b, int p) {
int s = 1;
for (; b; b >>= 1, a = 1ll * a * a % p) if (b & 1) s = 1ll * s * a % p;
return s;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int BSGS(int a, int b, int p) {
if (b == 1) return 0;
int cnt = 0, t = 1;
for (int g = gcd(a, p); g != 1; g = gcd(a, p)) {
if (b % p) return -1;
b /= g, p /= g, t = 1ll * t * (a / g) % p, cnt++;
if (b == t) return cnt;
}
static gp_hash_table<int, int> has; has.clear();
int m = (int)(sqrt(p) + 1), base = b;
for (int i = 0; i < m; i++) has[base] = i, base = 1ll * base * a % p;
base = ksm(a, m, p);
int now = t;
for (int i = 1; i <= m; i++) {
now = 1ll * now * base % p;
if (has[now]) return i * m - has[now] + cnt;
}
return -1;
}
signed main() {
int a, b, T;
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld", &a, &b);
--a;
int tb = b;
b = (p + (a + 1) * tb + a) % p;
int real_ans = p;
int ans = BSGS(a, b, p);
if (ans != -1 && ans % 2 == 1) {
real_ans = ans;
}
b = ((a + 1) * tb - a) % p;
ans = BSGS(a, b, p);
if (ans != -1 && ans % 2 == 0) {
real_ans = min(real_ans, ans);
}
if (real_ans == p) real_ans = -1;
printf("%lld\n", real_ans);
}
return 0;
}
1008. Maximal Submatrix
[title]
Given a n × m n\times m n × m matrix, find a maximum rectangle, so that each column is monotonic.
n , m ≤ 2000 n,m\leq 2000 n,m≤2000
[ideas]
Monotone stack classic problem.
Find out the length of the longest continuous non descent sequence down each position, then enumerate this position as the "narrowest" in the rectangle, and make a monotonic stack on the left and right.
Complexity O ( n m ) O(nm) O(nm)
[reference code]
/*
* @date:2021-07-20 12:13:04
* @source:
*/
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define For(i, x) for (int i = 0; i < (x); ++i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}
const int MAXN = 2e3 + 5;
int T, N, M;
vector<int> A[MAXN], H[MAXN];
void input() {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; ++i) {
A[i].resize(M);
for (int j = 0; j < M; ++j) {
scanf("%d", &A[i][j]);
}
}
for (int i = N - 1; i >= 0; --i) {
H[i].resize(M);
for (int j = 0; j < M; ++j) {
if (i == N - 1 || A[i + 1][j] < A[i][j]) H[i][j] = 1;
else H[i][j] = H[i + 1][j] + 1;
}
}
}
int l[MAXN], r[MAXN];
stack<int> area;
stack<int> stk;
int solve(vector<int> &height) {
while (!area.empty()) area.pop();
while (!stk.empty()) stk.pop();
int n = height.size();
for (int i = 0; i < n; i++) {
while (!area.empty() && height[i] < area.top()) {
r[stk.top()] = i;
area.pop();
stk.pop();
}
area.push(height[i]);
stk.push(i);
}
while (!stk.empty()) {
r[stk.top()] = n;
stk.pop();
area.pop();
}
for (int i = n - 1; i >= 0; --i) {
while (!area.empty() && height[i] < area.top()) {
l[stk.top()] = i;
area.pop();
stk.pop();
}
area.push(height[i]);
stk.push(i);
}
while (!stk.empty()) {
l[stk.top()] = -1;
stk.pop();
area.pop();
}
int ans = 0;
for (int i = 0; i < n; ++i)
chkMax(ans, height[i] * (r[i] - l[i] - 1));
return ans;
}
void solve() {
int ans = 0;
for (int i = 0; i < N; ++i) {
chkMax(ans, solve(H[i]));
}
printf("%d\n", ans);
}
int main() {
scanf("%d", &T);
while (T--) {
input();
solve();
}
return 0;
}
1009. KD-Graph
[title]
Give a pair n n n points m m The undirected graph with edge weight of m edges now requires you to determine a minimum D D D to put this n n n points are divided into K K Group K, meeting:
- There is a maximum edge weight of any point pair in the same group D D D path
- There is no one edge for any point pair in different groups, and the maximum edge weight does not exceed D D D path
n ≤ 1 0 5 , m ≤ 5 × 1 0 5 n\leq 10^5,m\leq 5\times 10^5 n≤105,m≤5×105
[ideas]
Obviously this D D The value of D can only be a certain edge weight (or 0 0 0), and then D D The larger D, K K K must not rise.
We enumerate this from childhood D D D. The current number of groups is exactly K K K is the answer, otherwise not.
Note that this is a forest, so the minimum number of groups is not necessarily 1 1 1
[reference code]
/*
* @date:2021-07-20 14:11:03
* @source:
*/
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define For(i, x) for (int i = 0; i < (x); ++i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}
int T, N, M, K;
map<int, vector<pii>> E;
vi Fa;
int findFa(int x) {
return Fa[x] == x ? x : Fa[x] = findFa(Fa[x]);
}
bool merge(int x, int y) {
x = findFa(x), y = findFa(y);
if (x == y) return false;
Fa[x] = y;
return true;
}
int main() {
scanf("%d", &T);
while (T--) {
E.clear();
scanf("%d%d%d", &N, &M, &K);
int u, v, w;
for (int i = 1; i <= M; ++i) {
scanf("%d%d%d", &u, &v, &w);
E[w].pb({u, v});
}
Fa.resize(N + 1);
for (int i = 1; i <= N; ++i) Fa[i] = i;
int cur = N;
if (K == N) {
printf("%d\n", 0);
continue;
}
bool flag = 0;
Trav(w, E) {
Trav(e, w.sec) {
cur -= merge(e.fir, e.sec);
}
if (cur == K) {
printf("%d\n", w.fir);
flag = 1;
break;
} else if (cur < K) {
printf("%d\n", -1);
flag = 1;
break;
}
}
if (!flag) puts("-1");
}
return 0;
}
1010. zoto
[title]
On a given plane n n n points, No i i The coordinates of i points are ( i , f [ i ] ) (i,f[i]) (i,f[i]), and then give m m m rectangles. How many rectangles are there in each rectangle y y y different points.
n , m , f [ i ] ≤ 1 0 5 n,m,f[i]\leq 10^5 n,m,f[i]≤105
[ideas]
First, if you just ask different questions y y The point of y is a classic scan line problem, but the requirements are different. In fact, the data structure is not easy to do, but we can consider another classic problem - asking for the number of different numbers in the interval, which is a Mo team problem.
Mo team is a modification O ( n n ) O(n\sqrt n) O(nn ) times, query O ( n ) O(n) O(n) times if we're right x x As a team of Mo, x becomes the above problem. We only need to reduce the complexity of single modification and spread it equally to the query.
Observed here f f f is very small. We can do it again f f f block, the number of maintenance and the number of different numbers in each block.
This is actually a classic block set block.
Complexity O ( ( n + m ) n ) O((n+m)\sqrt n) O((n+m)n )
[reference code]
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int B, V;
int t, n, m;
int bl[N], blv[N];
int ans[N], sum[N], sump[N], base[N];
struct query {
int id, l, r, a, b;
bool operator < (const query &x) const {
return (bl[l] ^ bl[x.l]) ? bl[l] < bl[x.l] : ((bl[l] & 1) ? r < x.r : r > x.r);
}
} q[N];
void del(int p) {
if (--sump[base[p]] <= 0) --sum[blv[base[p]]];
}
void add(int p) {
if (++sump[base[p]] <= 1) ++sum[blv[base[p]]];
}
int get(int l, int r) {
r = min(r, V);
if (l > V) return 0;
int nl = blv[l] + 1, nr = blv[r] - 1;
int ret = 0;
if (blv[l] == blv[r]) {
for (int i = l; i <= r; ++i) {
ret += (bool)sump[i];
}
} else {
for (int i = nl; i <= nr; ++i) ret += sum[i];
for (int i = l; blv[i] == blv[l] && l <= V; ++i) ret += (bool)sump[i];
for (int i = r; blv[i] == blv[r] && r >= 0; --i) ret += (bool)sump[i];
}
return ret;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
B = n / sqrt(m) + 1;
memset(sump, 0, sizeof sump);
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; ++i) {
scanf("%d", &base[i]);
V = max(V, base[i]);
bl[i] = i / B;
}
for (int i = 1, x0, y0, x1, y1; i <= m; ++i) {
scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
q[i].l = x0, q[i].r = x1;
q[i].a = y0, q[i].b = y1;
q[i].id = i;
}
sort(q + 1, q + m + 1);
int l = 1, r = 0; B = sqrt(V) + 1;
for (int i = 0; i <= V; ++i) blv[i] = i / B;
for (int i = 1; i <= m; ++i) {
int a = q[i].a, b = q[i].b;
while (l < q[i].l) del(l++);
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (r > q[i].r) del(r--);
ans[q[i].id] = get(a, b);
}
for (int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
return 0;
}
1011. Necklace of Beads
[title]
There are three kinds of RGB, three colors of beads to be strung into a length of n n n's necklace, RB has infinite, G has only k k k, how many essentially different schemes are there.
n , k ≤ 1 0 6 n,k\leq 10^6 n,k≤106
[ideas]
can't.
The solution is as follows:
[reference code]
#include<bits/stdc++.h>
using namespace std;
#define N 1000001
#define LL long long
#define MOD 998244353
LL n,k,ans,fac[N],inv[N],invfac[N],f[N],p[N],vis[N],prime[N],cnt,phi[N];
void pretype()
{
phi[1]=p[0]=fac[0]=invfac[0]=inv[1]=fac[1]=invfac[1]=1;
p[1]=2;
for(LL i=2;i<N;i++)
{
if(!vis[i])prime[++cnt]=i,phi[i]=i-1;
for(LL j=1;j<=cnt && i*prime[j]<N;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
p[i]=p[i-1]*2ll%MOD;
fac[i]=fac[i-1]*i%MOD;
inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
invfac[i]=invfac[i-1]*inv[i]%MOD;
}
}
LL C(LL n,LL m)
{
if(n<0 || m<0 || m>n)return 0;
return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;
}
LL get(LL n,LL k)
{
f[0]=n&1?0:2;
for(LL m=1;m<=n;m++)
f[m]=(p[m]*(C(n-m,m)+C(n-m-1,m-1))+f[m-1])%MOD;
return f[min(n,k)];
}
int main()
{
pretype();
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%lld%lld",&n,&k);
for(LL d=n;d>=1;d--)
if(n%d==0)
ans=(ans+phi[n/d]*get(d,k*d/n))%MOD;
printf("%lld\n",ans*inv[n]%MOD);
}
return 0;
}