This blog has been sitting in the background of my blog for several days, but I just remembered to post it today.
plant (plant)
First of all, when I saw the number of factors, I thought of considering the problem on the sequence after prime factorization. Further observation shows that the contribution of each dissimilar factor is independent.
In other words, when we consider the contribution of a certain prime factor to the answer alone, it is a question like this:
Given a sequence \(a\) of length \(n\) and a number \(w\), you can choose one \(i\) for each operation, let \(a_i \gets a_i + 1\), you can select the same position repeatedly. At most \(w\) operations, maximizing \(\prod\limits_{i=1}^n a_i\).
This is a classic problem, and it is easy to prove that the minimum value of each greedy operation is optimal. The data range is passed \(O(n^2)\), so it can be implemented in any way.
#define int long long
const int N=1e4 + 5,mod=998244353;
int n,w;
int a[N],cnt[N],ans=1;
priority_queue<int,vector<int>,greater<int> >q;
il void solve(int x,int sum)
{
for(int i=1;i<=n;i + + )
{
cnt[i]=1;
while(a[i]%x==0) cnt[i] + + ,a[i]/=x;
q.push(cnt[i]);
}
while(sum)
{
int x=q.top(); q.pop();
q.push(x + 1),sum--;
}
for(int i=1;i<=n;i + + ) ans=ans*q.top()%mod,q.pop();
}
signed main()
{
n=read(),w=read();
for(int i=1;i<=n;i + + ) a[i]=read();
for(int i=2;i*i<=w;i + + )
if(w%i==0)
{
int now=0;
while(w%i==0) now + + ,w/=i;
solve(i,now);
}
if(w>1) solve(w,1);
for(int i=1;i<=n;i + + )
{
for(int j=2;j*j<=a[i];j + + )
{
int now=1;
while(a[i]%j==0) a[i]/=j,now + + ;
ans=ans*now%mod;
}
if(a[i]>1) ans=ans*2%mod;
}
printf("%lld\\
",ans);
return 0;
}
woof (woof)
I feel that this structure is quite human-like. Maybe the brainwaves will match the person who asked the question.
I won’t base my approach on rigorous theory. Let’s briefly explain the process of guessing this thing.
First of all, we know that there are \(\dfrac{n(n-1)}{2}\) horizontally adjacent number pairs, \(\dfrac{n(n-1)}{2}\ \) essentially different binary groups. These two quantities are equal, which means that each essentially different pair appears exactly once on the board.
Then maybe try to classify these binary groups and place them in the same category.
After further guessing, I found: There are \(n-1\) pairs where the difference between two elements is \(1\), and there are \(n-2\ if the difference is \(2\) ) pairs, in the same way, there are \(1\) pairs whose difference is \(n-1\). We divide these pairs into groups of size \(1,2,\dots,n-1\).
Then you find that this exactly matches the number of adjacent pieces in each row on the chessboard!
But it’s not finished, because \((1,4),(2,5),(3,6),\dots\) obviously cannot be put on one line. Then continue to look for something that matches this grouping format.
Consider changing the direction. The number of pairs that can be placed in each column of the chessboard also satisfies this property.
That is to say, we try to put \(n-1\) number pairs with difference \(1\) in the \(1\)th column, and put \(2\) \(n-2\) number pairs whose difference is \(2\), and so on.
Knowing the general direction, we then consider the construction of each row, assuming that this row has \(n\) numbers. We want it to be shaped like the first pair of differences is \(1\), the second pair of differences is \(2\), and it should always be within the range of \([1,n]\), no matter It is difficult to think of an alternating structure of addition and subtraction.
Assuming the beginning is \(x\), then the value of this line is:
\[x\quad x + 1\quad x-1\quad x + 2\quad x-2\quad \dots\ \]
And because it is known that the numbers at the beginning of each line are different, we enumerate each \(x\) in turn and repeatedly construct the above sequence until it exceeds the range. For example \(n=7\), you can write:
\[\begin{aligned} & amp;1\quad 2\ & amp;2\quad 3\quad 1\quad 4\ & amp;3\quad 4\ \quad 2\quad 5\quad 1\quad 6\ &4\quad 5\quad 3\quad 6\quad 2\quad 7\quad 1\\ \ & amp;5\quad 6\quad 4\quad 7\quad 3\ & amp;6\quad 7\quad 5\ & amp;7\ \ \end{aligned} \]
Sort them in order of length and that’s the answer.
\[\begin{aligned} & amp;7\ & amp;1\quad 2\ & amp;6\quad 7\quad 5\ & amp;2\ \quad 3\quad 1\quad 4\ &5\quad 6\quad 4\quad 7\quad 3\ &3\quad 4\quad 2\quad 5\quad 1\quad 6\ &4\quad 5\quad 3\quad 6\quad 2\quad 7\quad 1\ \ \end{aligned} \]
Time complexity \(O(n^2)\).
const int N=4005;
int n,t,a[N][N];
int main()
{
n=read(),t=read();
for(int i=1;i<=n;i + + ,cout<<endl)
{
int st=(i & amp;1)?(2*n-i + 1)/2:(i>>1);
for(int j=1,len=1;j<=i;j + + ,len + + )
{
cout<<st<<" ";
if(j &1) st + =len; else st-=len;
}
}
return 0;
}
Challenge NPC IV (npc)
Part 1. \(k=1\)
First consider what to do when \(k=1\).
Considering how many intervals the final position \(i\) will be counted, it is not difficult to find that the number of times it is included in the contribution is \(b_i=i(n-i + 1)\).
In other words, the problem is transformed into, let \(a_i=f(i)\), \(b_i=i(n-i + 1)\), we need to specify an order for the \(a\) sequence , minimize \(\sum\limits_{i=1}^n a_i\times b_i\).
This problem is obviously greedy. The \(a\) sequence is sorted in ascending order, and the \(b\) sequence is sorted in descending order. The multiplication of the corresponding bits is the minimum value. The proof is easy: assuming \(a
Part 2. \(n\in [29,10^6]\)
A problem was discovered during the above process. The definition of essentially different solutions is that \(p\) is different, but there are many numbers in \(f(p_i)\) that are the same. Swapping some of them does not change the contribution sequence, but it does change \(p\). We therefore estimate that there are quite a few essentially different \(p\) without changing the contribution sequence.
Consider estimating this specific number, there are approximately \(\frac{n}{2}\) \(1\) in the \(a\) sequence, \(\frac{n} {2^2}\) \(2\) (let’s not discuss the issue of rounding up and down for now), then we can at least come up with $cnt=\prod\limits_{i=1}^{\ \log_2 n} (\frac{n}{2^i})! $ permutations that obtain the minimum value. This does not take into account the case of swapping \(b\) sequences, so the actual value will be more than this.
This shows that the answer can be the minimum value when \(k\le cnt\). Write a code to find the above formula, and you can find that when \(n=29\), \(cnt\) exceeds \(10^{18}\). That is, when \(n>29\), the answer to any value of \(k\) is equal to \(k=1\).
\(O(n)\) simulation of the above greedy, with explosive search can pass the first \(13\) points. There are 52pts of violence points, good conscience!
Part 3. \(n\in [29,10^{18}]\)
There is no separate part for this part, but we need to speed up the greedy process.
As long as you quickly find the number of each number in the \(a\) sequence, you can find their corresponding continuous interval in the \(b\) sequence. Based on the knowledge of basic bit operations, the number of occurrences of the value \(i\) can be obtained.
Let \(s(l,r)=\sum\limits_{i=l}^r b_i\), and push the formula:
\[\begin{aligned} s(l,r) & amp;=\sum_{i=l}^r i(n-i + 1)\ & amp;=(n + 1)(\ sum_{i=l}^r i)-\sum_{i=l}^r i^2\ & amp;=(n + 1)\frac{(l + r)(r-l + 1)} {2} – \frac{r(r + 1)(2r + 1)}{6} + \frac{l(l-1)(2l-1)}{6} \end{aligned} \ \]
Now both sequences are fast to compute and we can handle a single query in \(O(\log n)\) time complexity.
Part 4. \(n\le 28\)
It seems that there are still many such numbers even if only considering essentially different \(a\) sequences. But we discovered a key property: in this case, the value range of gracefulness is very small, only about \(10^4\).
Consider doing a dp based on this. Observe further that there are at most \(5\) different values in the \(a\) sequence. Since gracefulness is already factored into the state, we obviously only care about how many of them are filled in, not where they are.
Therefore, suppose \(f_{a,b,c,d,e,sum}\) represents \(1,2,3,4,5\) and fill in \(a,b,c, d,e\) The number of solutions with a total gracefulness of \(sum\).
The formula for enumerating what number to fill in the current position during transfer is easy to write.
The number of such valid states reaches the upper bound when \(n=28\), which is roughly \(16\times 9\times 5\times 3\times 2\times 1.1\times 10^4=4.752\times 10^7\) states. Please pay attention to space consumption when opening an array.
Combine this with Part 3 to get 100pts.
#define int long long
const int N=1e6 + 5,mod=998244353;
int T,n,k;
int f[16][9][5][3][2][11005];
int a[N],b[N],cnt[N],mx=11000,now[6],jc[N];
il int qpow(int n,int k=mod-2)
{
int res=1;
for(;k;n=n*n%mod,k>>=1) if(k & amp;1) res=res*n%mod;
return res;
}
il int S(int x) {x%=mod;return x*(x + 1)%mod*(2*x + 1)%mod*qpow(6)%mod;}
il int get(int l,int r,int n)
{
if(l>r) return 0;
if(r>n/2 & amp; & amp;l<=n/2) return (get(l,n/2,n) + get(n/2 + 1,r,n))%mod;
if(l>n/2) l=n-l,r=n-r,swap(l,r);
int res=n%mod*((l + r)%mod)%mod*((r-l + 1)%mod)%mod*qpow(2)%mod-(S(r)-S(l-1) + mod)%mod;
return (res%mod + mod)%mod;
}
il void solve(int n)
{
int l=1,r=n,res=0;
for(int i=__lg(n) + 1;i;i--)
{
int sum=(n>>i) + (n>>(i-1) & amp;1);
int ls=sum/2,rs=sum-ls;
if(l<n-r + 1) swap(ls,rs);
(res + =i*get(l,l + ls-1,n + 1)%mod)%=mod,(res + =i*get(r-rs + 1,r,n + 1)%mod) %=mod;
l + =ls,r-=rs;
}
printf("%lld\\
",res);
}
signed main()
{
T=read(); jc[0]=1;
for(int i=1;i<=15;i + + ) jc[i]=jc[i-1]*i;
while(T--)
{
n=read(),k=read();
if(n>28) {solve(n);continue;}
for(int i=1;i<=n;i + + ) a[i]=1 + __lg(i & amp;(-i));
for(int i=1;i<=n;i + + ) b[i]=i*(n-i + 1);
sort(a + 1,a + n + 1),sort(b + 1,b + n + 1);
for(int i=1;i<=n;i + + ) cnt[i]=0;
for(int i=1;i<=n;i + + ) cnt[a[i]] + + ;
int Cnt=1;
if(n<=28) for(int i=1;i<=__lg(n) + 1;i + + ) Cnt=Cnt*jc[cnt[i]];
f[0][0][0][0][0][0]=1;
for(now[1]=0;now[1]<=cnt[1];now[1] + + )
for(now[2]=0;now[2]<=cnt[2];now[2] + + )
for(now[3]=0;now[3]<=cnt[3];now[3] + + )
for(now[4]=0;now[4]<=cnt[4];now[4] + + )
for(now[5]=0;now[5]<=cnt[5];now[5] + + )
{
int sum=0;
for(int i=1;i<=5;i + + ) sum + =now[i];
if(!sum) continue;
for(int j=0;j<=mx;j + + )
{
int i=0;
for(int k=1;k<=5;k + + )
{
if(now[k]==0) continue;
if(j-k*b[sum]<0) continue;
now[k]--;
i + =f[now[1]][now[2]][now[3]][now[4]][now[5]][j-k*b[sum]];
now[k] + + ;
}
f[now[1]][now[2]][now[3]][now[4]][now[5]][j]=i;
}
}
int ans=0;
for(int i=0;i<=mx;i + + )
{
ans + =Cnt*f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i];
if(ans>=k) {printf("%lld\\
",i);break;}
}
}
return 0;
}
Four Dark Carvings Alone Riding (mahjong)
Part 1. \(O(nm)\)
Let’s first observe some basic properties of the topic.
- Cards are drawn alternately, so who draws each card is fixed.
- Because the two cards in everyone’s hand will not be the same during the game (otherwise it will be over), they will definitely not play the same card as their opponent’s hand. So the final way to tie the cards must be that one person draws the same card as himself from the pile.
- Consider the situation where two people have the same cards. Neither of them can discard this card, otherwise the opponent will win. Therefore, the outcome of this situation can be determined directly: just determine who draws the next identical card. If not, it is a draw.
So, if a person wants to draw cards, his strategy must be to hold a certain card from a certain moment until the next one is the same.
Consider the effect of someone holding the \(i\)th card all the time:
- If the next card of the same color is touched by yourself, let its position be \(x\). Then the result of holding this card is victory at \(x\) moment.
- If the next card of the same color is touched by the opponent, the opponent must not discard this card. Therefore, both sides have the same cards, and the outcome has been determined.
- The next card was touched by ourselves, but since the opponent has no chance to come back from the moment \(x\), we record its result as a direct victory at the moment \(x\).
- If touched by the opponent, the result is recorded as failure at \(x\) moment.
- Otherwise, a tie is reached at time \(x\).
Then we can simulate this process in the sequence. If the effect of the card is victory, choose the one that wins earlier; if it fails, choose the one that loses later, because you may get a winning card later and turn the tables. If the moment of victory or defeat for a card in someone’s hand has been reached, the answer is determined.
However, it is not correct to do this directly. Poor Ying Xuemiao wrote for a whole day and still couldn’t figure out what was wrong.
Consider a set of data like this: the deck is \(3,1,4,3,4\), and the initial hand is \(1,2\).
Whether Alice changes the cards to \(3\) in the first round, it will be a draw. She prefers to wait until later to win. If Bob hopes to win later and does not choose to replace \(2\) with \(1\), he will only fail in the end. And if his goal is a draw, he will take \(1\) from the deck and successfully draw.
This inspires us to think about a question: There are some situations where if a person’s goal is to win, he will lose; but if his goal is just to maintain a draw, he can successfully prevent the opponent from winning. This cannot be judged directly by greed.
Consider changing their goal as follows: first decide that a draw counts as Alice winning, which is equivalent to Alice’s goal being to keep the tie. If Bob can still win at this time, it is considered that Bob must win. Vice versa.
If both pros and cons are met, then there is a way for the loser to keep the tie, and the answer is a draw.
If you don’t understand the details clearly, it’s easy to write false information. You can refer to the code to understand.
const int N=2e5 + 5;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
if(qwq==pos[x].end()||(*qwq)>r) return -1;
return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
int qwq=find(x,l + fg,r);
if(qwq==-1) return (l & amp;1)==flag?n + 1:-n-1;
if((qwq & amp;1)==(l & amp;1)) return qwq;
int nqwq=find(x,qwq,r);
if(nqwq==-1) return (l & amp;1)==flag?qwq:-qwq;
else if((nqwq & amp;1)==(l & amp;1)) return qwq;
else return -qwq;
}
il int solve(int x,int y,int l,int r)
{
if(x==y)
{
int nxt=find(x,l-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt & amp;1)==(l & amp;1)) return 1;
else return -1;
}
int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
for(int i=l;i<=r;i + + )
{
if(wx==i) return 1; if(wy==i) return -1;
if(-wx==i) return -1; if(-wy==i) return 1;
if(x==y)
{
int nxt=find(x,i-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt & amp;1)==(l & amp;1)) return 1;
else return -1;
}
if((i & amp;1)==(l & amp;1))
{
int nxt=getw(a[i],i,r);
if(nxt>0 & amp; & amp;(nxt<wx||wx<0)) wx=nxt,x=a[i];
else if(nxt<0 & amp; & amp;wx<0 & amp; & amp;nxt<wx) wx=nxt,x=a[i];
}
else
{
int nxt=getw(a[i],i,r);
if(nxt>0 & amp; & amp;(nxt<wy||wy<0)) wy=nxt,y=a[i];
else if(nxt<0 & amp; & amp;wy<0 & amp; & amp;nxt<wy) wy=nxt,y=a[i];
}
}
return flag?1:-1;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i + + ) a[i]=read(),pos[a[i]].push_back(i);
while(m--)
{
id++;
int x=read(),y=read(),l=read(),r=read();
flag=1; int res1=solve(x,y,l,r);
flag=0; int res0=solve(x,y,l,r);
if(res1==-1) printf("B\\
");
else if(res0==1) printf("A\\
"); else printf("D\\
");
}
return 0;
}
Part 2. \(O((n + m)\log n)\)
Assuming that the outcome of each card has been determined, it is still not easy to quickly maintain the answer, because if you lose, you have to lose as late as possible, and if you win, you have to win as early as possible.
We continue to observe properties.
Note that when the time comes to determine the answer for a certain hand card, the winning card must be the winning card. In other words, a person will not always hold a losing card until he loses because of this card.
Consider proving this conclusion. Suppose Alice now holds a losing card in her hand and is about to lose in the next round; at this time she draws another losing card. Because these two cards are different, their losing positions must also be different. Then the newly drawn card must be lost later than the original one. Whenever this happens, Alice changes the cards to ensure that she never loses because of the losing cards.
Of course, here we have to specifically judge the situation of losing in the first round with the initial hand, because they have no choice at this time.
Therefore, we only need to determine who touched the earliest winning card within a certain interval.
Consider offline interrogation, scanning \(r\) from left to right. For the card at position \(i\), its contribution is only related to whether the next identical card and the next identical card are within the interval. Therefore, the contribution of a card will only change \(3\) times, and a new value can be obtained violently every time it is modified.
Then for each query, the earliest winning card is the position of the minimum value in the interval, and just determine the parity of the position of this card.
We need a data structure to support single-point modification and interval query of the minimum value and the position of the minimum value. Line segment tree maintenance is used here.
const int N=2e5 + 5,inf=1e9;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
if(qwq==pos[x].end()||(*qwq)>r) return -1;
return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
int qwq=find(x,l + fg,r);
if(qwq==-1) return inf;
if((qwq & amp;1)==(l & amp;1)) return qwq;
int nqwq=find(x,qwq,r);
if(nqwq==-1) return (l & amp;1)==flag?qwq:inf;
else if((nqwq & amp;1)==(l & amp;1)) return qwq;
else return inf;
}
struct segtree
{
struct node{int mn,pos;} tr[N<<2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l + r>>1)
il node pushup(const node & amp;l,const node & amp;r)
{
if(l.mn<r.mn) return l;
else return r;
}
void build(int x,int l,int r)
{
if(l==r) {tr[x]={inf,l};return;}
build(ls,l,mid),build(rs,mid + 1,r);
tr[x]=pushup(tr[ls],tr[rs]);
}
void upd(int x,int l,int r,int p,int k)
{
if(l==r) {tr[x]={k,l};return;}
if(p<=mid) upd(ls,l,mid,p,k);
else upd(rs,mid + 1,r,p,k);
tr[x]=pushup(tr[ls],tr[rs]);
}
node query(int x,int l,int r,int ml,int mr)
{
if(l==ml & amp; & amp;r==mr) return tr[x];
if(mr<=mid) return query(ls,l,mid,ml,mr);
else if(ml>mid) return query(rs,mid + 1,r,ml,mr);
else return pushup(query(ls,l,mid,ml,mid),query(rs,mid + 1,r,mid + 1,mr));
}
}seg;
int ans[2][N];
vector<int> nd[N];
struct node{int x,y,l,r,id;};
vector<node> q[N];
il int calc(int x,int y,int l,int r)
{
if(x==y)
{
int nxt=find(x,l-1,r);
if(nxt==-1) return flag?1:-1;
else if((nxt & amp;1)==(l & amp;1)) return 1;
else return -1;
}
if(y==a[l])
{
int nxt=find(y,l,r);
if(nxt!=-1 & amp; & amp;((nxt & amp;1)==(l & amp;1))) return 1;
else if(nxt==-1) return flag?1:-1;
}
int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
int ans=min(wx,wy),pos=(wx<wy)?l-2:l-1;
segtree::node qwq=seg.query(1,1,n,l,r);
if(qwq.mn<ans) ans=qwq.mn,pos=qwq.pos;
if(ans==inf) return flag?1:-1;
return ((l & amp;1)==(pos & amp;1))?1:-1;
}
void solve()
{
seg.build(1,1,n);
for(int r=1;r<=n;r + + )
{
for(auto x:nd[r]) seg.upd(1,1,n,x,getw(a[x],x,r));
for(auto i:q[r])
{
int x=i.x,y=i.y,l=i.l,r=i.r,id=i.id;
ans[flag][id]=calc(x,y,l,r);
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i + + ) a[i]=read(),pos[a[i]].push_back(i);
for(int i=1;i<=m;i + + )
{
int x=read(),y=read(),l=read(),r=read();
q[r].push_back({x,y,l,r,i});
}
for(int i=1;i<=n;i + + )
{
int nxt=find(a[i],i,n);
if(nxt==-1) continue;
nd[nxt].push_back(i);
int nnxt=find(a[i],nxt,n);
if(nnxt!=-1) nd[nnxt].push_back(i);
}
for(flag=0;flag<2;flag + + ) solve();
for(int i=1;i<=m;i + + )
{
if(ans[1][i]==-1) printf("B");
else if(ans[0][i]==1) printf("A");
else printf("D");
printf("\\
");
}
return 0;
}
I wish everyone who sees this NOIP 2023 RP + + >w<
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57580 people are learning the system