We observe that when there is $$$0$$$ in the sequence, it is optimal to choose $$$0$$$ and any number other than $$$0$$$ for each operation.

Therefore, when there is $$$0$$$ in the sequence, let $$$cnt$$$ be the number of $$$0$$$s, the answer is $$$n - cnt$$$.

Otherwise, when $$$0$$$ does not exist in the sequence, there are two situations:

1. When there exist two equal numbers in the sequence, we can perform the operation $$$1$$$ time to convert it into the situation of having $$$0$$$ in the sequence. So the answer must be $$$n$$$.

2. When all numbers in the sequence are distinct, we can perform the operation $$$2$$$ times to convert it into the situation of having $$$0$$$ in the sequence. So the answer must be $$$n + 1$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n;
		scanf("%i",&n);
		vector<int> a(n);
		for(int i=0;i<n;i++)
			scanf("%i",&a[i]);
		sort(a.begin(),a.end());
		int zero=count(a.begin(),a.end(),0);
		if(zero>0)
			printf("%i\n",n-zero);
		else{
			bool same=false;
			for(int i=1;i<n;i++)
				if(a[i]==a[i-1])
					same=true;
			if(same)printf("%i\n",n);
			else printf("%i\n",n+1);
		}
	}
	return 0;
}

• Good problem

• Average problem

• Bad problem

Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $$$0$$$ or $$$1$$$. In other words, the string is divided into many adjacent binaries with length of $$$2$$$. If the binary is "01" or "10", it needs $$$1$$$ operation, otherwise the operation is not required.

If you want to minimize the number of "contiguous segments", a simple greedy way is to change each "binary requiring operation" (i.e. $$$01$$$ or $$$10$$$) into the form of the previous or next "binary requiring no operation" (i.e. $$$11$$$ or $$$00$$$). For example: "0010" change to "0000" and "1101" change to "1111". In this way, this "binary requiring operation" has no contribution to the final number of contiguous segments. We only need to count the number of contiguous "11" and "00" binaries.

In particular, if all binaries are "01" or "10", the final contribution to the number of final contiguous segments is $$$1$$$ in total.

Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $$$0$$$ or $$$1$$$. In other words, the string is divided into many adjacent binaries with length of $$$2$$$.

Consider the recursion from the front to the back, it can be observed that the previously maintained prefix must end with "00" or "11". Therefore, it's necessary to convert each divided binary into "00" or "11" by enumerating the cost of changing the current binary into "00" and "11". Maintain the minimum number of operations in the process of DP, try to make the current string consistent with the end of the prefix subsegment.

$$$dp[n][2]$$$, set the first dimension as the maintained length of prefix and the second dimension as the suffix state of the prefix.

Then the DP transfer equation is:

where $$$c_k$$$ represents the cost of converting the current binary to "kk".

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    for (cin >> t; t; t -= 1) {
        int n, L = -1, x = 0, y = 0;
        string s;
        cin >> n >> s;
        for (int i = 0; i < n; i += 2) {
            if (s[i] != s[i + 1]) x += 1;
            else {
                if (L != s[i]) y += 1;
                L = s[i];
            }
        }
        cout << x << " " << max(y, 1) << "\n";
    }
}

#include<bits/stdc++.h>
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
#define lowit(x) (x&-x)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                             \
    std::ios::sync_with_stdio(false);   \
    std::cin.tie(nullptr);              \
    std::cout.tie(nullptr);
    
using namespace std;

typedef long long ll;
typedef pair<ll,ll> PII;

inline ll read(){
	ll x=0;char ch;bool f=true;
	for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
	for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return f?x:-x;
}
//#define LOCAL_DEFINE
#define DEBUG(x) cerr<<(#x)<<'='<<(x)<<endl
const int N=2e5+7;
const int INF=1e9;
char s[N];
int c[N];
PII dp[N][2];
void solve(){
	int n=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)s[i]-='0';
	for(int i=1;i<=n/2;i++)c[i]=s[i*2]+s[i*2-1]*2;
	for(int i=1;i<=n/2;i++)for(int j=0;j<2;j++)dp[i][j]={INF,INF};
	for(int i=1;i<=n/2;i++)for(int j=0;j<2;j++){
		int cc=c[i],dd=j?3:0,cnt=((dd%2)^(cc%2))+((dd/2)^(cc/2));
		for(int k=0;k<2;k++)
			dp[i][j]=min(dp[i][j],{dp[i-1][k].first+cnt,dp[i-1][k].second+(j!=k)});
	}
	PII ans=min(dp[n/2][0],dp[n/2][1]);
	cout<<ans.first<<" "<<ans.second+1<<"\n";
}

int main(){
	#ifdef ONLINE_JUDGE
	#else	
		//fre("1");
	#endif
	ll T=1;
	T=read();
	for(int i=1;i<=T;i++)solve();
	#ifdef LOCAL_DEFINE
    	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	#endif
	return 0;
}

• Good problem

• Average problem

• Bad problem

• Good problem

• Average problem

• Bad problem

We can calculate the answer in two steps.

The first step, for each $$$b$$$, let $$$f_b$$$ represents the number of $$$p_d$$$ where $$$p_b > p_d$$$ in the interval $$$[b+1,n]$$$. We can calculate $$$f$$$ in $$$\mathcal{O}(n^2)$$$.

The second step, calculate the answer. First we enumerate $$$c$$$ from $$$1$$$ to $$$n$$$, and then enumerate $$$a$$$ from $$$1$$$ to $$$c-1$$$. When $$$p_a < p_c$$$, add $$$f_b$$$ in the interval $$$[a+1,c-1]$$$ to the answer. Before enumerating $$$a $$$, we can calculate the prefix sum of $$$f$$$ first, so we can add the $$$f_b$$$ in the interval to the answer in $$$\mathcal{O}(1)$$$. The time complexity of this step is $$$\mathcal{O}(n^2)$$$. However, this will add the result of $$$d$$$ in the interval $$$[a+1,c-1]$$$ to the answer, which is illegal because $$$c < d$$$ is required. So we need to maintain $$$f$$$ while enumerating $$$c$$$: enumerate $$$b$$$ from $$$1$$$ to $$$c-1$$$, if $$$p_b > p_c$$$, $$$f_b$$$ minus $$$1$$$. $$$p_c$$$ is actually regarded as $$$p_d$$$, that is, subtract the case where $$$c$$$ is equal to $$$d$$$, so as to subtract the illegal case. The time complexity of this step is also $$$\mathcal{O}(n^2)$$$.

Time complexity:$$$\mathcal{O}(n^2)$$$.

By the way, use Fenwick Tree or Segment Tree can also pass, the time complexity is $$$\mathcal{O}(n^2 log\ n)$$$

#include <bits/stdc++.h>
using namespace std;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
	int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
	return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze 
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/*************  debug end  *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII > VPII;
/************* define end  *************/
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end  ***************/
void go();
int main(){
	#ifdef tokitsukaze
		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=998244353;
/*********************************  head  *********************************/
int a[MAX];
ll f[MAX],bitf[MAX];
void go()
{
	int n,i,j,k,l,T;
	ll ans;
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&a[i]);
		mem(f,0);
		for(j=1;j<=n;j++)
		{
			for(l=j+1;l<=n;l++)
			{
				if(a[j]>a[l]) f[j]++;
			}
		}
		ans=0;
		for(k=1;k<=n;k++)
		{
			for(j=1;j<k;j++)
			{
				if(a[j]>a[k]) f[j]--;
			}
			bitf[0]=0;
			for(i=1;i<=k;i++) bitf[i]=bitf[i-1]+f[i];
			for(i=1;i<k;i++)
			{
				if(a[i]<a[k]) ans+=bitf[k-1]-bitf[i];
			}
		}
		printf("%lld\n",ans);
	}
}

• Good problem

• Average problem

• Bad problem

Obviously, we can calculate the answers of rows and columns separately.

For the answers of columns, we can observe that since there are only $$$n \cdot m$$$ students in total, no students will leave, and every time a new student entering the meeting hall, all columns will move one step to the right circularly, so the answer will not decrease. If the $$$i$$$-th student is a serious student, for all the previous students with subscript $$$j$$$ where $$$0 < j < i$$$, and $$$j \% m = i \% m$$$ are naughty students, the answer in the column will increase by $$$1$$$.

For the answer of rows, we can transfer it from the answer of $$$i-m$$$, which is equivalent to adding a new row to the answer of $$$i-m$$$. Suppose the last serious student is the $$$j$$$-th student. If $$$i-j<m$$$, the answer will increase by $$$1$$$, otherwise the answer will be the same as that of when the $$$i-m$$$ student enters the meeting hall.

#include<bits/stdc++.h>
using namespace std;
int rownum[1000100];
int col[1000100];
int n,m;
void init(){
	for(int i = 0;i <= max(n,m);i++) {
		rownum[i] = col[i] = 0;
	}
}
void solve(){
	scanf("%d%d",&n,&m);
	init();
	int las = -n*m;
	int colnum = 0;
	char tmp;
	for(int i = 0;i < n*m;i++) {
		scanf(" %c",&tmp);
		tmp -= '0';
		if(tmp == 1) {
			las = i;
			if(col[i%m] == 0) {
				col[i%m] = 1;
				colnum++;
			}
		}
		if(i - las < m) {
			rownum[i%m]++;
		}
		if(i!=0) printf(" ");
		printf("%d",rownum[i%m] + colnum);
		
	}
	printf("\n");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--) {
		solve();
	}
} 

• Good problem

• Average problem

• Bad problem

First, find the cycle directly, take out all the cycles, and then fill each cycle in the order: maximum, minimum, maximum, minimum $$$ \ldots $$$.

Note that when you encounter an odd cycle, the last one should be empty and fill in the middle value.

For example, in a ternary cycle, if the first and the second position are filled with $$$1$$$ and $$$9$$$, it can be observed that the contribution of the ternary cycle to the answer remains unchanged no matter which number between $$$2 \sim 8$$$ is filled in the middle. So this situation can be left out first, and finally fill in whatever number is left. The same to the cycles with odd sizes such as self cycles and five membered cycles, because the last number does not provide any contribution. In this way, you can directly construct a solution with the maximum $$$score$$$.

We notice that if we take out the numbers that has already been filled in each cycle and put them into a new cycled array $$$h$$$, in fact, the numbers providing contribution are only at the "peak" and "valley" points of the array. We define "peak" as the point with subscript $$$i$$$ where $$$h_{i}>h_{i-1}$$$ and $$$h_{i}>h_{i+1}$$$, and "valley" is the point with subscript $$$i$$$ where $$$h_{i}<h_{i-1}$$$ and $$$h_{i}<h_{i+1}$$$. Obviously, each "peak" will provide contribution of $$$2 \cdot h_{i}$$$, each "valley" will provide contribution of $$$-2 \cdot h_{i}$$$. For the points which are neither "peak"s nor "valley"s, they do not provide any contribution.

In order to maximize the score, we make the larger number in the permutation "peak" and the smaller number "valley". There are $$$\left \lfloor \frac{CircleSize}{2} \right \rfloor$$$ "peak"s and "valley"s for a circle with a length of $$$Circlesize$$$.

So the expression of the final answer can be derived from the summation formula of the arithmetic sequence:

Let $$$c=\sum \left \lfloor \frac{CircleSize}{2} \right \rfloor$$$, $$$N$$$ represents the size of the permutation, $$$score=2c \cdot (N-c)$$$.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n,col[2][MAXN],col_to_pos_1[MAXN];
long long output;
bool vis_0[MAXN];
int T,cnt;
long long c;
void dfs(int pos)
{
	if(vis_0[pos])return;
	vis_0[pos]=true;
	++cnt;
	dfs(col_to_pos_1[col[0][pos]]);
}
int main(int argc, char const *argv[])
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			vis_0[i]=false;
		}
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&col[0][i]);
		}
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&col[1][i]);
			col_to_pos_1[col[1][i]]=i;
		}
		c=0;
		for(int i=1;i<=n;++i)
		{
			cnt=0;
			dfs(i);
			c+=cnt/2;
		}
		printf("%lld\n", (c*(n-c))<<1);
	}
	
	return 0;
}

• Good problem

• Average problem

• Bad problem

Consider finding out the relationship between sequence $$$v$$$ and permutation $$$p$$$. It can be observed that the permutation $$$p$$$ have bijective relationship with sequence $$$c$$$. That is to say, sequence $$$c$$$ will only correspond to one permutation $$$p$$$, as it can be proved:

Let $$$S={1,2,\ldots,n}$$$, and find that the last number can be determined through $$$c_n$$$, because there is no number after this position. We observe that $$$p_n$$$ is the $$$(c_n+1)$$$ largest number in $$$S$$$, then delete $$$p_n$$$ from $$$S$$$, we can get $$$p_{n - 1}$$$. So repeat the process, we can get the whole permutation.

Consider counting $$$v$$$, we observe that each bubble sort will first make $$$v_i=\max(v_{i}-1,0)$$$, then the whole $$$v$$$ moves left, $$$v_1$$$ is directly covered, $$$v_n$$$ is set to $$$0$$$. Because each valued $$$v_i$$$ is preceded by a number larger than the current position, then it will definitely be exchanged and moved forward, $$$v_i$$$ minus $$$1$$$.

For example, if the current $$$v=[0,0,2,1,1]$$$, after once bubble sort, $$$v=[0,1,0,0,0]$$$.

To avoid confusion, the $$$V$$$ array below is the $$$v$$$ in the input. It's easy to count after knowing the above conclusion.

For the position $$$i(i\le k)$$$, it can be observed that after $$$k$$$ times of bubble sort , it is directly covered, so just multiply the answer by $$$\prod_{i=1}^k i$$$.

For the position $$$i(k\lt i \le n)$$$, if $$$V_{i-k}\ne -1$$$, then obviously $$$v_i$$$ is uniquely determined; If $$$V_{i-k}=-1$$$, then $$$v_i$$$ has $$$i$$$ possible values, multiply the answer by $$$i$$$; If $$$V_{i-k}=0$$$, then $$$v_i-k\le 0$$$, multiply the answer by $$$k+1$$$.

Note that for the position $$$i(i\ge n-k+1)$$$, $$$V_i$$$ should be $$$0$$$ or $$$-1$$$, otherwise the answer must be $$$0 $$$.

Complexity:$$$\mathcal{O}(n)$$$.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<ctime>
#include<cmath>
#include<unordered_map> 
using namespace std;
#define LL long long
#define pp pair<int,pair<int,int>>
#define mp make_pair 
#define fi first
#define se second.first
#define th second.second
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T> void gi(T& x){
		x=0; int f=1;char c=gc();
		if(c=='-')f=-1;
		for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
		x=x*f;
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void pi(T x,char c='\n'){
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
using IO::pc;
int t,n,a[1000005],ans,k;
const int mod=998244353;
signed main(){
	srand(time(0));
	gi(t);
	while(t--){
		gi(n),gi(k);
		bool f=0;
		for(int i=1;i<=n;i++)gi(a[i]),f|=(a[i]>i-1);
		if(f){
			pi(0,'\n');
			continue;
		}
		ans=1;
		for(int i=1;i<=k;i++)ans=1ll*ans*i%mod;
		for(int i=n-k+1;i<=n;i++){
			if(a[i]!=-1&&a[i]){
				pi(0,'\n');
				f=1;
				break;
			}
		}
		if(f)continue;
		for(int i=k+1;i<=n;i++){
			int limit=i-1;
			if(a[i-k]==-1){
				ans=1ll*ans*i%mod;
			}else{
				if(a[i-k]){
					limit=a[i-k]+k;
					if(limit>i-1)f=1;
				}
				else {
					limit=min(limit,k),ans=1ll*ans*(limit+1)%mod; 
				}	
			}
		}
		if(f)ans=0;
		pi(ans,'\n');
	} 
	return 0;
}

• Good problem

• Average problem

• Bad problem

Let's sort the queries $$$[l,r]$$$ with $$$r$$$ in ascending order.

Let's move $$$R$$$ from $$$1$$$ to $$$n$$$, and answer queries $$$[l,r]$$$ when $$$r=R$$$.

Use segment tree to solve this problem, each leaf node $$$[ul,ul]$$$ in the segment tree maintenance the number that how many intervals $$$[ul,R]$$$ are beautiful, then answering queries is to get sum.

Use monotone stack to maintain the maximum number. When moving $$$R$$$ one step right, the monotone stack will pop some and push one.

Let's think about the number $$$x$$$ in monotone stack, which means the maximum number of the intervals $$$[lp,R]$$$ ($$$l1 \le lp \le l2$$$) is $$$x$$$. If there exist a $$$ll$$$ in $$$[l1,l2]$$$ which satisfies $$$a_{ll}*a_R=x$$$, then before $$$x$$$ is poped, intervals $$$[l,rr]$$$ are beautiful($$$l \in [l1,l2]$$$,$$$l \le ll$$$ ,$$$R \le rr$$$).

So we can assume that $$$x$$$ will not be poped when it is pushed in the monotone stack, and do something like difference algorithm in the segment tree, by using the current $$$R$$$ as the time stamp. Each node in the segment tree has to maintain $$$a*R+b$$$,which like a linear function.

So when moving $$$R$$$ right step, let's enumerate the factor of $$$a_R$$$ to update old intervals in monotone stack, enumerate the multiple of $$$a_R$$$ to update the new interval in monotone stack and update the intervals which are poped.

Time complexity: $$$\mathcal{O}(nlognlogn+qlogn)$$$.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef pair<int,int> pp;
int n,m,ti,top,a[N],d[N],p[N],bz[N],bo[N];
long long ans[1000005];
vector<pp>q[1000005];
vector<int>w[N];
struct dd
{
	long long x,y,tg,len;
}tr[N*4];
void make(int x,int l,int r)
{
	tr[x].len=r-l+1;
	if (l==r) return;
	int mid=l+r>>1;
	make(x<<1,l,mid),make(x<<1|1,mid+1,r);
}
void down(int x)
{
	if (tr[x].x==tr[x].len)
	{
		tr[x<<1].x=tr[x<<1].len;
		tr[x<<1|1].x=tr[x<<1|1].len;
	}
	if (tr[x].x==0)
	{
		tr[x<<1].x=0;
		tr[x<<1|1].x=0;
	}
	tr[x<<1].tg+=tr[x].tg;
	tr[x<<1].y+=tr[x].tg*tr[x<<1].len;
	tr[x<<1|1].tg+=tr[x].tg;
	tr[x<<1|1].y+=tr[x].tg*tr[x<<1|1].len;
	tr[x].tg=0;
}
void up(int x)
{
	tr[x].x=tr[x<<1].x+tr[x<<1|1].x;
	tr[x].y=tr[x<<1].y+tr[x<<1|1].y;
}
void clear(int x,int l,int r,int ll,int rr)
{
	if (l>=ll && r<=rr)
	{
		tr[x].tg+=ti;
		tr[x].y+=ti*tr[x].len;
		tr[x].x=0;
		return;
	}
	down(x);
	int mid=l+r>>1;
	if (ll<=mid) clear(x<<1,l,mid,ll,rr);
	if (rr>mid) clear(x<<1|1,mid+1,r,ll,rr);
	up(x);
}
void add(int x,int l,int r,int ll,int rr)
{
	if (l>=ll && r<=rr)
	{
		tr[x].tg-=ti;
		tr[x].x=tr[x].len;
		tr[x].y-=ti*tr[x].len;
		return;
	}
	down(x);
	int mid=l+r>>1;
	if (ll<=mid) add(x<<1,l,mid,ll,rr);
	if (rr>mid) add(x<<1|1,mid+1,r,ll,rr);
	up(x);
}
long long find(int x,int l,int r,int ll,int rr)
{
	if (l>=ll && r<=rr) return tr[x].y+ti*tr[x].x;
	down(x);
	int mid=l+r>>1;
	long long ans=0;
	if (ll<=mid) ans+=find(x<<1,l,mid,ll,rr);
	if (rr>mid) ans+=find(x<<1|1,mid+1,r,ll,rr);
	return ans;
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),bz[a[i]]=i;
	for (int i=1;i<=m;i++) 
	{
		int l,r;
		scanf("%d%d",&l,&r);
		q[r].emplace_back(l,i);
	}
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j+=i)
		w[j].emplace_back(i);
	make(1,1,n);
	for (int i=1;i<=n;i++)
	{
		while (top && a[d[top]]<a[i])
		{
			if (p[top]>d[top-1]) clear(1,1,n,d[top-1]+1,p[top]);
			bo[d[top]]=0;
			top--;
		}
		for (int j=a[i];j<=n;j+=a[i])
		if (bo[bz[j]])
		{
			int pt=bo[bz[j]];
			int l=d[pt-1]+1,r=d[pt];
			int e=bz[j/a[i]];
			if (e<l || e>=i) continue;
			e=min(e,r);
			if (e<=p[pt]) continue;
		//	if (l<=p[pt]) clear(1,1,n,l,p[pt]);
			add(1,1,n,p[pt]+1,e);
			p[pt]=e;
		}
		d[++top]=i;
		bo[i]=top;
		p[top]=d[top-1];
		for (auto j:w[a[i]])
		{
			int l=d[top-1]+1,r=i;
			int e1=bz[j],e2=bz[a[i]/j];
			if (e2<=e1) continue;
			if (e1<l || e2>i) continue;
			if (e1<=p[top]) continue;
		//	if (l<=p[top]) clear(1,1,n,l,p[top]);
			add(1,1,n,p[top]+1,e1);
			p[top]=e1;
		}
		ti++;
		for (auto t:q[i]) ans[t.second]=find(1,1,n,t.first,i);
	}
	for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);	
	return 0;
}

• Good problem

• Average problem

• Bad problem

First, consider how to calculate the contribution of a legal path. It can be found that the contribution of a legal path is equivalent to the following formula, where $$$b_i$$$ indicates the number of the $$$i$$$-th gems on the path.

This formula seems impossible to calculate, but it can be observed that there is a chain structure behind it. Consider dynamic programming, try to calculate the $$$1\sim (i+1)$$$-th gems' answer by only considering the $$$1\sim i$$$-th gems' answer. Consider maintenance these:

$$$dp_{n,1}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(\sum_{j=1}^n (P^{i_j}i_j^k)\times\sum_{j=1}^n [i_j\ne 0])$$$

$$$dp_{n,2}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}\sum_{j=1}^n (P^{i_j}i_j^k)$$$

$$$dp_{n,3}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n} \sum_{j=1}^n [i_j\ne 0]$$$

$$$dp_{n,4}=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n} 1$$$

It can be observed that if we enumerate how many the $$$(n + 1)$$$-th gem are selected, this can actually be transferred, for example:

$$$dp_{n+1,1}=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}((\sum_{j=1}^n P^{i_j}i_j^k+P^p p^k)\times (\sum_{j=1}^n [i_j\ne 0])+[p\ne 0])$$$

Then spread.

$$$A=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(\sum_{j=1}^n P^{i_j}i_j^k \times \sum_{j=1}^n [i_j\ne 0])=(1+b_{n+1})dp_{n,1}$$$

$$$B=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}\sum_{j=1}^n P^{i_j}i_j^k[p\ne 0]=b_{n+1}dp_{n,2}$$$

$$$C=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}P^p p^k\times \sum_{j=1}^n [i_j\ne 0]=dp_{n,3} \times \sum_{p=0}^{b_{n+1}}P^p p^k=dp_{n,3} \times \sum_{p=1}^{b_{n+1}}P^p p^k$$$

$$$D=\sum_{p=0}^{b_{n+1}}\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\ldots \sum_{i_n=0}^{b_n}(P^p p^k)\times [p\ne 0]=dp_{n,4}\times\sum_{p=1}^{b_{n+1}}P^p p^k$$$

Now it can be transferred. The main problem is how to calculate $$$\sum_{i=1}^n i^kx^i$$$ quickly, ensuring that $$$x\gt 1$$$.

Let $$$h_{k,n}$$$ represent $$$\sum_{i=1}^n i^k x^i$$$.

Calculate the sum according to the proportional sequence, $$$h_{0,n}=\dfrac{x^{n+1}-x}{x-1}$$$.

Finally we get

According to this recurrence formula, we can get

When $$$k$$$ is constant, there exist a $$$k$$$-degree polynomial $$$g_k(x)$$$ about $$$n$$$, making $$$h_{k,n}=x^{n+1}g_k(n)-xg_k(0)$$$. This conclusion can be proved by mathematical induction.

Consider how to use interpolation to get this polynomial, we only need to find $$$g_k(0)\sim g_k(k)$$$.

Consider difference method, $$$h_{k,n}-h_{k,n-1}=x^{n+1}g_k(n)-x^ng_k(n-1)=n^kx^n$$$.

So $$$xg_k(n)-g_k(n-1)=n^k$$$. But we still can't get $$$C$$$. There is a conclusion: the $$$(n + 1)$$$-th difference of the $$$n$$$-degree polynomial $$$f(x)$$$ is $$$0$$$. That is to say, $$$\sum_{i=0}^{n+1}(-1)^{n+1-i}\binom{n+1}{i}f(i)=0$$$.

So we can get $$$g_k(0)$$$, then use polynomial fast interpolation, and then polynomial multipoint evaluation to get the value of every point we need.

It can be observed that the DP transfer can be replaced by matrix, so there are matrices each position, the problem is equivalent to get the sum of the matrix products of all intervals. It's easy to solve. You can solve it in the way you like.

Overall complexity: $$$\mathcal{O}(k\log^2k+n)$$$.

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<assert.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define int long long
const int MAXN=4e5+5;
const int MAXNN=1e5+5;
int n,k,P,fac[MAXN],ifac[MAXN],Inv[MAXN],rev[MAXN],x[MAXN],y[MAXN],K[MAXN],B[MAXN],g[MAXN],F[MAXN],Q[MAXN],val[MAXN]; 
int a[MAXNN],b[MAXNN],W[21][MAXN*2];
const int mod=998244353;
vector<int>G[MAXNN];
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int dec(int a,int b){return ((a-b)%mod+mod)%mod;}
inline int add(int a,int b){return ((a+b)%mod+mod)%mod;}
inline int qkpow(int a,int b){
	int ans=1,base=a;
	while(b){
		if(b&1)ans=mul(ans,base);
		base=mul(base,base);
		b>>=1;
	}
	return ans;
}
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T> void gi(T& x){
		x=0; char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void pi(T x,char c='\n'){
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
using IO::pc;
const int S=4;
struct Matrix{
	int a[4][4];
	Matrix(){memset(a,0,sizeof a);}
	void clear(){memset(a,0,sizeof a);}
	void init(){for(int i=0;i<S;i++)a[i][i]=1;}
	int* operator [] (int x){return a[x];}
	Matrix friend operator +(Matrix A,Matrix B){
		Matrix ret=Matrix();
		for(int i=0;i<S;i++)
			for(int j=0;j<=i;j++)
				ret[i][j]=add(A[i][j],B[i][j]);	
		return ret;
	}
	Matrix friend operator -(Matrix A,Matrix B){
		Matrix ret=Matrix();
		for(int i=0;i<S;i++)
			for(int j=0;j<=i;j++)
				ret[i][j]=dec(A[i][j],B[i][j]);	
		return ret;
	}
	Matrix friend operator *(Matrix A,Matrix B){
		Matrix ret=Matrix();
		for(int k=0;k<S;k++)
			for(int j=0;j<=k;j++)
				if(B[k][j])
					for(int i=k;i<S;i++)
						ret[i][j]=1ll*(ret[i][j]+1ll*A[i][k]*B[k][j])%mod;	
		return ret;
	}
	Matrix friend operator *(Matrix A,int x){
		Matrix ret=Matrix();
		for(int i=0;i<S;i++)
				for(int j=0;j<=i;j++)
					ret[i][j]=1ll*A[i][j]*x%mod;
		return ret;
	}
}d[MAXNN],dp[MAXNN],ans;
Matrix operator += (Matrix &p,Matrix q){return p=p+q;}
Matrix operator -= (Matrix &p,Matrix q){return p=p-q;}
Matrix operator *= (Matrix &p,Matrix q){return p=p*q;}
inline int C(int n,int m){
	if(n<m||m<0)return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void init(){
	fac[0]=ifac[0]=Inv[0]=Inv[1]=1;
	for(int i=1;i<MAXN;i++)fac[i]=1ll*fac[i-1]*i%mod; 
	ifac[MAXN-1]=qkpow(fac[MAXN-1],mod-2);
	for(int i=MAXN-2;i>=1;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
    for(int i=2;i<MAXN;i++)Inv[i]=1ll*(mod-mod/i)*Inv[mod%i]%mod;
    int wn;
    for(int i=0,x=1;x<MAXN;i++,x<<=1){
        W[i][x]=1;
        wn=qkpow(3,(mod-1)/(x<<1));
        for(int j=1;j<x;j++)W[i][x+j]=1ll*wn*W[i][x+j-1]%mod;
        wn=qkpow(wn,mod-2);
        for(int j=1;j<x;j++)W[i][x-j]=1ll*wn*W[i][x-j+1]%mod;
    } 
} 
inline void NTT(int *a,int type,int n){
    for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    LL x,y;
    for(int i=1,cnt=0;i<n;cnt++,i<<=1){
        for(int j=0;j<n;j+=(i<<1)){
            for(int t=0,k=j;k<j+i;k++,t+=type){
                x=a[k],y=1ll*W[cnt][i+t]*a[k+i];
                a[k]=(x+y)%mod;
                a[k+i]=(x-y)%mod;
            }
        }
    }
    if(type==-1)for(int i=0;i<n;i++)a[i]=mul(a[i],Inv[n]);
}
void Polyinv(int *a,int *b,int len){
	static int c[MAXN];
	if(len==1){
		b[0]=qkpow(a[0],mod-2);
		return ;
	}
	Polyinv(a,b,(len+1)>>1);
	int l=0,m=(len<<1),n=1;
	for(;n<=m;n<<=1,l++);
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=0;i<len;i++)c[i]=a[i];
	for(int i=len;i<n;i++)c[i]=0;
	NTT(c,1,n),NTT(b,1,n);
	for(int i=0;i<n;i++)b[i]=1ll*(2-1ll*b[i]*c[i])%mod*b[i]%mod;
	NTT(b,-1,n);
	for(int i=len;i<n;i++)b[i]=0;
}
inline void Polydao(int *Aa,int *Bb,int len){
	Bb[len-1]=0;
	for(int i=1;i<len;i++)Bb[i-1]=1ll*i*Aa[i]%mod;
}
int init_NTT(int L){
	int l=0,m=L,n=1;
	for(;n<=m;n<<=1,l++);
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	return n;
}
void MUL(int *a,int *b,int *c,int n,int m,int lim){
	static int t1[MAXN],t2[MAXN],t3[MAXN];
	for(int i=0;i<n;i++)t1[i]=a[i];
	for(int i=0;i<m;i++)t2[i]=b[i];
	for(int i=n;i<lim;i++)t1[i]=0;
	for(int i=m;i<lim;i++)t2[i]=0;
	NTT(t1,1,lim),NTT(t2,1,lim);
	for(int i=0;i<lim;i++)t3[i]=1ll*t1[i]*t2[i]%mod;
	NTT(t3,-1,lim);
	for(int i=0;i<n+m-1;i++)c[i]=t3[i]; 
}
namespace Evaluation{
	#define ls(p) p<<1
	#define rs(p) p<<1|1
	int *T1[MAXN],*T2[MAXN],T3[MAXN],T4[MAXN],flow[MAXN*32],*now=flow;
	void clear(){now=flow;}
	inline void MUL2(int *a,int *b,int *c,int n,int m,int lim){
		static int t1[MAXN],t2[MAXN],t3[MAXN];
		for(int i=0;i<n;i++)t1[i]=a[i];
		for(int i=0;i<m;i++)t2[i]=b[i];
		reverse(t2,t2+m);
		for(int i=n;i<lim;i++)t1[i]=0;
		for(int i=m;i<lim;i++)t2[i]=0;
		NTT(t1,1,lim),NTT(t2,1,lim);
		for(int i=0;i<lim;i++)t3[i]=1ll*t1[i]*t2[i]%mod;
		NTT(t3,-1,lim);
		for(int i=m-1;i<n;i++)c[i-m+1]=t3[i]; 
	}
	void pre(int *Q,int p,int l,int r){
		T1[p]=now,now+=r-l+2;
		T2[p]=now,now+=r-l+2;
		for(int i=0;i<=r-l+1;i++)T1[p][i]=T2[p][i]=0;
		if(l==r){
			T1[p][0]=1;
			T1[p][1]=(mod-Q[l])%mod;
			return ; 
		}
		int mid=(l+r)>>1;
		pre(Q,ls(p),l,mid);
		pre(Q,rs(p),mid+1,r);
		if(r-l+1<=256){
			for(int i=0;i<=mid-l+1;i++)
				for(int j=0;j<=r-mid;j++)
					T1[p][i+j]=add(T1[p][i+j],1ll*T1[ls(p)][i]*T1[rs(p)][j]%mod);
		}else{
			int lim=init_NTT(r-l+1);
			MUL(T1[ls(p)],T1[rs(p)],T1[p],mid-l+2,r-mid+1,lim); 
		}
	}
	void Solve(int *S,int p,int l,int r){
		if(l==r){
			S[l]=T2[p][0];
			return ;
		}
		int mid=(l+r)>>1;
		int lim=init_NTT(r-l+1);
		MUL2(T2[p],T1[rs(p)],T2[ls(p)],r-l+1,r-mid+1,lim);
		MUL2(T2[p],T1[ls(p)],T2[rs(p)],r-l+1,mid-l+2,lim);
		Solve(S,ls(p),l,mid);
		Solve(S,rs(p),mid+1,r);
	}
	//opt0/1 区分多点求值/快速插值 
	void evaluation(int *F,int *Q,int *S,int n,int m,int opt){
		clear();
		static int AF[MAXN];
		n=max(n,m+1),m=max(m,n-1);
		pre(Q,1,1,m);
		if(opt){
			for(int i=0;i<n;i++)AF[i]=T1[1][i];
			reverse(AF,AF+n); 
			Polydao(AF,AF,n+1);
		}
		Polyinv(T1[1],T3,m+1);
		reverse(T3,T3+m+1);
		int lim=init_NTT(n+m+1); 
		if(!opt)MUL(F,T3,T4,n,m+1,lim);
		else MUL(AF,T3,T4,n,m+1,lim);
		for(int i=n;i<n+m;i++)T2[1][i-n]=T4[i];
		Solve(S,1,1,m);
		for(int i=1;i<=m;i++)S[i]=(1ll*S[i]*Q[i]%mod+(!opt?F[0]:AF[0]))%mod;
		for(int i=0;i<=n+m+1;i++)T3[i]=T4[i]=0;
	}
};
namespace Lagrange_Interpolation{
	#define ls(p) p<<1
	#define rs(p) p<<1|1
	int S[MAXN],*T[MAXN],flow[MAXN*32],*now=flow,tmp1[MAXN],tmp2[MAXN],e1[MAXN],e2[MAXN];
	void solve(int p,int l,int r){
		T[p]=now,now+=r-l+2;
		if(l==r){
			T[p][0]=S[l];
			return ;
		}
		int mid=(l+r)>>1;
		solve(ls(p),l,mid);
		solve(rs(p),mid+1,r);
		for(int i=0;i<mid-l+1;i++)tmp1[i]=T[ls(p)][i];
		for(int i=0;i<r-mid;i++)tmp2[i]=T[rs(p)][i];
		for(int i=0;i<r-mid+1;i++)e1[i]=Evaluation::T1[rs(p)][i];
		reverse(e1,e1+r-mid+1);
		for(int i=0;i<mid-l+2;i++)e2[i]=Evaluation::T1[ls(p)][i];
		reverse(e2,e2+mid-l+2);
		int lim=init_NTT(r-l+1); 
		MUL(tmp1,e1,e1,mid-l+1,r-mid+1,lim);
		MUL(tmp2,e2,e2,r-mid,mid-l+2,lim);
		for(int i=0;i<=r-l;i++)T[p][i]=add(e1[i],e2[i]);
	}
	void Interpolation(int *x,int *y,int *ans,int n){
		Evaluation::evaluation(x,x,S,n+1,n,1);
		for(int i=1;i<=n;i++)S[i]=1ll*y[i]*qkpow(S[i],mod-2)%mod;
		solve(1,1,n);
		for(int i=0;i<n;i++)ans[i]=T[1][i];
	}
}
void Pre(int P){
	int	invP=qkpow(P,mod-2),kk=0,bb=0;
	K[0]=1,B[0]=0;
	for(int i=1;i<=k+1;i++){
		K[i]=1ll*K[i-1]*invP%mod;
		B[i]=1ll*(B[i-1]+qkpow(i,k))*invP%mod;
		int Num=C(k+1,i);
		if(i&1)kk=dec(kk,1ll*Num*K[i]%mod),bb=dec(bb,1ll*Num*B[i]%mod);
		else kk=add(kk,1ll*Num*K[i]%mod),bb=add(bb,1ll*Num*B[i]%mod);
	} 
	kk=(kk+1),kk=(kk==mod?0:kk);
	g[0]=1ll*(mod-bb)*qkpow(kk,mod-2)%mod;
	for(int i=1;i<=k;i++)g[i]=add(1ll*g[0]*K[i]%mod,B[i]);
	for(int i=1;i<=k+1;i++)x[i]=i-1,y[i]=(g[i-1]+mod)%mod;
	Lagrange_Interpolation::Interpolation(x,y,F,k+1);
	for(int i=0;i<=k;i++)F[i]=(F[i]+mod)%mod; 
//	cout<<endl;
	for(int i=1;i<=n;i++)Q[i]=b[i];
	Evaluation::evaluation(F,Q,val,k+1,n,0);
	for(int i=1;i<=n;i++)val[i]=(val[i]+mod)%mod;
}
inline void makeit(int Id,int y,Matrix& S){
	//[S1S2,S1,S2,product of b]
	int X=dec(1ll*qkpow(P,y+1)*val[Id]%mod,1ll*P*g[0]%mod);
	S.a[0][0]=add(y,1),S.a[1][0]=y,S.a[2][0]=X,S.a[3][0]=X;
	S.a[1][1]=add(y,1),S.a[3][1]=X;
	S.a[2][2]=add(y,1),S.a[3][2]=y; 
	S.a[3][3]=add(y,1);
} 
signed main(){
	gi(n),gi(k),gi(P);
	init();
	for(int i=1;i<=n;i++)gi(b[i]);
	Pre(P);
	for(int i=1;i<=n;i++)makeit(i,b[i],d[i]);
	dp[1]=d[1];
	for(int i=2;i<=n;i++)dp[i]=dp[i-1]*d[i]+d[i];
	for(int i=1;i<=n;i++)ans+=dp[i];
	pi(ans.a[3][0],'\n');
	return 0;
}

• Good problem

• Average problem

• Bad problem

Just enumerating the increment can pass.

However, by increasing at most $$$2$$$ points, the value of her HP can always become an odd number, and thus the highest possible level is either $$$A$$$ or $$$B$$$. We can just solve case by case.

#include<cstdio>
int x,i,A;char B;
char cal(int x){
  x%=4;
  if(x==0)return 'D';
  if(x==1)return 'A';
  if(x==2)return 'C';
  return 'B';
}
int main(){
  scanf("%d",&x);
  A=0;
  B=cal(x);
  for(i=1;i<=2;i++){
    if(cal(x+i)<B){
      A=i;
      B=cal(x+i);
    }
  }
  printf("%d %c",A,B);
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int x;
	cin>>x;
	if(x%4==0) puts("1 A");
	else if(x%4==1) puts("0 A");
	else if(x%4==2) puts("1 B");
	else if(x%4==3) puts("2 A");
	return 0;
}

There are only two types of mentsus, so you can enumerate the mentsu you want her to form, and check the difference between that and those currently in her hand.

Alternatively, you can find out that the answer is at most $$$2$$$, since she can draw two extra identical tiles which are the same as one of those in her hand. You may enumerate at most $$$1$$$ extra tile for her and check if it can contribute to a mentsu. If she can't, the answer will be $$$2$$$.

#include <bits/stdc++.h>
using namespace std;
int main() {
	int idx[257] = {}, c[3][9] = {}, ans = 2;
	idx['m'] = 1;
	idx['p'] = 2;
	idx['s'] = 3;
	for(int i = 0; i < 3; ++i) {
		char buf[3];
		scanf("%s", buf);
		++c[idx[buf[1]] - 1][buf[0] - '1'];
	}
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 9; ++j) {
			ans = min(ans, 3 - c[i][j]);
			if(j + 2 < 9)
				ans = min(ans, 3 - !!c[i][j] - !!c[i][j + 1] - !!c[i][j + 2]);
		}
	printf("%d\n", ans);
	return 0;
}

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 y00
 
//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll bt = 30;
const ld eps = 1e-7;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(1e9 + 239);
const int MOD = 998244353;
const ll MOD2 = (ll)MOD * (ll)MOD;
 
//random
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());
 
//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 20);
const int B = (int)sqrt(M);
const int X = 1e4 + 239;
 
bool check(string a, string b, string c)
{
    if (a == b && b == c) return true;
    if (a > b) swap(a, b);
    if (b > c) swap(b, c);
    if (a > b) swap(a, b);
    if (a[1] == b[1] && b[1] == c[1])
    {
        if (a[0] + 1 == b[0] && b[0] + 1 == c[0])
            return true;
    }
    return false;
}
 
int32_t main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    if (check(a, b, c))
    {
        cout << "0";
        return 0;
    }
    vector<string> var;
    for (int i = 1; i <= 9; i++)
    {
        string s = "";
        s += (char)(i + '0');
        var.push_back(s + "m");
        var.push_back(s + "p");
        var.push_back(s + "s");
    }
    for (string s : var)
    {
        if (check(s, a, b))
        {
            cout << "1";
            return 0;
        }
        if (check(s, a, c))
        {
            cout << "1";
            return 0;
        }
        if (check(s, b, c))
        {
            cout << "1";
            return 0;
        }
    }
    cout << "2";
    return 0;
}

The order of discarding is given, so we can simulate the process of discarding.

In each time, we can calculate the page that contains the first special item that has not been discarded, and then locate all the special items that need to be discarded at one time. Repeat this process until all special items are discarded.

Each time at least one item would be discarded, so the time complexity is $$$\mathcal{O}(m)$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+10;
ll p[MAX];
int main()
{
	ll n,m,k;
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;i++) scanf("%lld",&p[i]);
	int ans=0;
	int sum=0;
	int now=1;
	while(now<=m)
	{
		ll r=((p[now]-sum-1)/k+1)*k+sum;
	//	cout<<"r:"<<r<<endl;
		while(now<=m&&p[now]<=r)
		{
			sum++;
			now++;
		}
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Unless the first player must lose after the first move, the numbers of stones in these piles should form a permutation obtained from $$$0$$$ to $$$(n - 1)$$$ in the end, in order to ensure that there are no two piles include the same number of stones.

Let's use $$$cnt[x]$$$ to represent the number of piles which have exactly $$$x$$$ stones in the beginning. There are four cases that Tokitsukaze will lose after the first move:

• $$$cnt[0] > 1$$$;
• $$$cnt[x] > 2$$$ for some $$$x$$$;
• $$$cnt[x] > 1$$$ and $$$cnt[y] > 1$$$ for some $$$x$$$, $$$y$$$ ($$$x \neq y$$$);
• $$$cnt[x] > 1$$$ and $$$cnt[x - 1] > 0$$$ for some $$$x$$$.

If Tokitsukaze won't lose after the first move, then we only need to check the parity of the total number of stones that can be taken.

By the way, if you don't want to discuss the above four cases, you can just enumerate her first move.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+10;
int a[MAX];
int main()
{
	int n;
	cin>>n;
	map<int,int> mp;
	int ok=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
		ok&=(mp[a[i]]<3); //situation 1: one >=3 
	}
	int cnt=0;
	for(auto it:mp)
	{
		if(it.second>=2) cnt++;
	}
	ok&=(cnt<=1);// situation 2: more than two >=2
	for(auto it:mp)
	{
		if(it.second==2)
		{
			ok&=(mp.count(it.first-1)==0);// situation 3: reduce one but add another
			if(it.first==0) ok=0;// situation 4: two pile is zero
		} 
	}
	if(!ok) return 0*puts("cslnb");
	// normal situation 
	sort(a+1,a+1+n);
	ll s=0;
	for(int i=1;i<=n;i++)
	{
		assert(a[i]>=i-1);
		s+=a[i]-(i-1);
	}
	s%=2;
	return 0*puts(s?"sjfnb":"cslnb");
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5 + 1;
int n, a[maxn], c[3];
void update(int x, int d) {
	static map<int, int> ctr;
	int &v = ctr[x];
	--c[min(v, 2)];
	v += d;
	++c[min(v, 2)];
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", a + i);
		update(a[i], 1);
	}
	bool chk = 0;
	for(int i = 0; !chk && i < n; ++i)
		if(a[i]) {
			update(a[i], -1);
			update(a[i] - 1, 1);
			chk |= !c[2];
			update(a[i] - 1, -1);
			update(a[i], 1);
		}
	if(chk) {
		chk = 0;
		for(int i = 0; i < n; ++i)
			chk ^= (a[i] + i) & 1;
	}
	puts(chk ? "sjfnb" : "cslnb");
	return 0;
}

If a player can make a move from a situation to that situation again, this player will not lose. Except for some initial situations, one can move from almost every situation to itself. Based on these two conclusions, we can get a solution.

If Tokitsukaze cannot win after her first move, she cannot win in the future. In this case, we can quickly check if $$$k$$$ is so limited that she cannot win.

After her first move, it is possible that Quailty wins in the next move. If he cannot, in order to prevent failure, he can just leave the situation to his opponent by doing useless flipping and thus result in a draw.

Therefore, we can check if no matter how Tokitsukaze moves, Quailty has no chance to win after his first move. It can be easily checked linearly if we do some precalculation and enumerate Tokitsukaze's first move. Alternatively, we can find and check the pattern of initial situations in which Quailty can win.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,k;
char str[MAXN];
vector<int> loc[2];
int main()
{
    scanf("%d%d%s",&n,&k,str);
    for(int i=0;i<n;i++)
        loc[str[i]-'0'].push_back(i);
    if(loc[0].empty() || loc[1].empty())
        return 0*printf("tokitsukaze\n");
    int flag=0;
    for(int l=0,r=k-1;r<n;l++,r++)
    {
        vector<int> tmp[2];
        for(int i=0;i<2;i++)
        {
            if(loc[i].front()<l || loc[i].front()>r)
                tmp[i].push_back(loc[i].front());
            if(loc[i].back()<l || loc[i].back()>r)
                tmp[i].push_back(loc[i].back());
            auto itr=lower_bound(loc[i].begin(),loc[i].end(),l);
            if(itr!=loc[i].begin())
                tmp[i].push_back(*--itr);
            itr=upper_bound(loc[i].begin(),loc[i].end(),r);
            if(itr!=loc[i].end())
                tmp[i].push_back(*itr);
            sort(tmp[i].begin(),tmp[i].end());
        }
        if(tmp[0].empty() || tmp[1].empty())
            return 0*printf("tokitsukaze\n");
        flag|=(tmp[0].back()-tmp[0].front()>=k
            || tmp[1].back()-tmp[1].front()>=k);
    }
    return 0*printf("%s\n",(flag ? "once again" : "quailty"));
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5 + 1;
int n, m, p[maxn], lft[maxn], rht[maxn];
char buf[maxn];
int main() {
	scanf("%d%d%s", &n, &m, buf);
	for(int i = 0, las[2] = {-1, -1}; i < n; ++i) {
		int o = buf[i] - '0';
		lft[i] = las[o ^ 1];
		las[o] = i;
	}
	for(int i = n - 1, las[2] = {n, n}; i >= 0; --i) {
		int o = buf[i] - '0';
		rht[i] = las[o ^ 1];
		las[o] = i;
	}
	bool fir = 0, sec = 1;
	for(char op = '0'; op <= '1' && !fir; ++op) {
		int sz = 0;
		for(int i = 0; i < n; ++i)
			if(buf[i] != op)
				p[sz++] = i;
		for(int L = 0, R = m - 1, pL = 0, pR = -1; R < n; ++L, ++R) {
			for( ; pL < sz && p[pL] < L; ++pL);
			for( ; pR + 1 < sz && p[pR + 1] <= R; ++pR);
			if(pL == 0 && pR == sz - 1) {
				fir = 1;
				break;
			}
			int uL = p[pL ? 0 : pR + 1];
			int uR = p[pR < sz - 1 ? sz - 1 : pL - 1];
			int vL = uL > 0 ? 0 : min(rht[uL], uR + 1);
			int vR = uR < n - 1 ? n - 1 : max(lft[uR], uL - 1);
			sec &= uR - uL + 1 <= m || vR - vL + 1 <= m;
		}
	}
	puts(fir ? "tokitsukaze" : (sec ? "quailty" : "once again"));
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int n,k,T;
int a[MAXN],sum[MAXN];
int q_sum(int l,int r)
{
    if(l>r)return 0;
    return sum[r]-sum[l-1];
}
bool check_fir()
{
    for(int i=1;i+k-1<=n;++i)
    {
        int lala=q_sum(1,i-1)+q_sum(i+k,n);
        if(lala==0||lala+k==n)return true;
    }
    return false;
}
bool check_sec()
{
    if(k*2<n||k==1)return false;
    int len=n-k-1;
    for(int i=2;i<=len;++i)
    {
        if(a[i]!=a[i-1]||a[n-i+1]!=a[n-i+2])return false;
    }
    if(a[len]==a[len+1]||a[n-len]==a[n-len+1]||a[1]==a[n])return false;
    return true;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%1d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    if(check_fir())
    {
        printf("tokitsukaze\n");
    }
    else
    {
        if(check_sec())
        {
            printf("quailty\n");
        }
        else
        {
            printf("once again\n");
        }
    }
    return 0;
}

For each strange rectangular area and its corresponding set of points, we only need to focus on the lowest $$$y$$$-coordinate $$$yB$$$, the leftmost $$$x$$$-coordinate $$$xL$$$ and the rightmost $$$x$$$-coordinate $$$xR$$$ of points in this set. Different sets must have different $$$yB$$$, $$$xL$$$, $$$xR$$$, so we can count them by enumerating these values.

Let's enumerate $$$yB$$$ first. Then, we need to list all the possible $$$x$$$-coordinates of points $$$(x_i, y_i)$$$ satisfying that $$$y_i \geq yB$$$ and mark every possible $$$x'$$$ satisfying there is a point $$$(x', yB)$$$. By doing so, we can make sure when enumerating $$$xL$$$ and $$$xR$$$, the requirement for $$$yB$$$ is met as well. However, enumerating forcibly, which is in time complexity $$$\mathcal{O}(n^3)$$$, is too slow to pass, so let's optimize the enumeration step by step.

Let's pick and sort the points $$$(x'_1, yB), (x'_2, yB), \ldots, (x'_m, yB)$$$ from left to right. Assuming that $$$x'_0 = 0$$$, and $$$(x'_j, yB)$$$ is the leftmost point of them that is in the chosen set, we can count the number of aforementioned different $$$x$$$-coordinates in ranges $$$[x'_{j - 1} + 1, x'_j]$$$ and $$$[x'_j, \infty)$$$ and then count the number of possible pairs $$$(xL, xR)$$$ immediately. More specifically, let $$$cnt(l, r)$$$ be the number of different $$$x$$$-coordinates of points in the area $$$\lbrace (x, y) | l \leq x \leq r, y \geq yB \rbrace$$$, and we know the number of possible pairs $$$(xL, xR)$$$ is $$$cnt(x'_{j - 1} + 1, x'_j) \cdot cnt(x'_j, \infty)$$$. After precalculating $$$c(1, x)$$$ for each $$$yB$$$, we can reduce the time complexity into $$$\mathcal{O}(n^2)$$$.

The very last step is using the trick of sweeping lines. We can enumerate $$$yB$$$ from highest to lowest, and during that process, use data structures to maintain possible $$$x$$$-coordinates. What we need to implement is to maintain a container, check if a coordinate is already in the container, add a coordinate to the container, and query the number of coordinates in a range. These requirements can be easily achieved by Fenwick tree, segment tree or others. With the last optimization, we can solve in time complexity $$$\mathcal{O}(n \log n)$$$.

By the way, there also exist solutions using other approaches, such as divide and conquer.

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
	#ifdef tokitsukaze
//		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=998244353;
/*********************************  head  *********************************/
struct Fenwick_Tree
{
	int bit[MAX];
	int n;
	void init(int _n){n=_n;mem(bit,0);}
	int lowbit(int x){return x&(-x);}
	void insert(int x,int v)
	{
		while(x<=n)
		{
			bit[x]+=v;
			x+=lowbit(x);
		}
	}
	int get(int x)
	{
		int res=0;
		while(x)
		{
			res+=bit[x];
			x-=lowbit(x);
		}
		return res;
	}
	int query(int l,int r)
	{
		return get(r)-get(l-1);
	}
}tr;
VI x[MAX],y;
void go()
{
	int n,i,tot,pre;
	ll ans;
	while(~scanf("%d",&n))
	{
		tr.init(n);
		y.clear();
		map<int,int> idx,idy,cntx;
		tot=0;
		for(i=0;i<n;i++)
		{
			int X,Y;
			scanf("%d%d",&X,&Y);
			if(!idy.count(Y))
			{
				x[tot].clear();
				idy[Y]=tot++;
				y.pb(Y);
			}
			x[idy[Y]].pb(X);
			cntx[X]++;
		}
		tot=0;
		for(auto it:cntx)
		{
			idx[it.fi]=++tot;
			tr.insert(tot,1);
		}
		sort(all(y));
		ans=0;
		for(auto Y:y)
		{
			sort(all(x[idy[Y]]));
			pre=1;
			for(auto X:x[idy[Y]])
			{
				ans+=1LL*tr.query(pre,idx[X])*tr.query(idx[X],tot);
				pre=idx[X]+1;
				cntx[X]--;
				if(cntx[X]==0)
				{
					cntx.erase(X);
					tr.insert(idx[X],-1);
				}
			}
		}
		printf("%lld\n",ans);
	}
}

#include <bits/stdc++.h>
using namespace std;
//priority_queue<int> q;
//priority_queue<int,vector<int>, greater<int> > q;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> less_rbtree;
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> greater_rbtree;

typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> multi_less_rbtree;
typedef tree<pair<int,int>, null_type, greater<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> multi_greater_rbtree;
const int MAXN=300005;
less_rbtree div_tree;
long long ans;
struct node
{
    int x,y;
}p[MAXN],temp[MAXN];
int n;
bool cmp1(const node & A,const node & B)
{
    return A.x<B.x;
}
bool cmp2(const node & A,const node & B)
{
    if(A.y!=B.y)return A.y>B.y;
    return A.x<B.x;
}
void div_algorithm(int l,int r)
{
    if(l>r)return;
    div_tree.clear();
    for(int i=l;i<=r;++i)
    {
        temp[i]=p[i];
    }
    int mid_line=p[(l+r)>>1].x;
    long long preans=ans;
    int lpos=-1,rpos=-1;
    sort(temp+l,temp+r+1,cmp2);
    for(int i=l;i<=r;++i)
    {
        div_tree.insert(temp[i].x);
        if(temp[i].x<=mid_line)
        {
            if(lpos==-1||lpos<temp[i].x)
            {
                lpos=temp[i].x;
            }
        }
        if(temp[i].x>=mid_line)
        {
            if(rpos==-1||rpos>temp[i].x)
            {
                rpos=temp[i].x;
            }
        }
        if(i==r||temp[i+1].y!=temp[i].y)
        {

            long long lsum=div_tree.order_of_key(lpos+1);
            long long Lsum=div_tree.order_of_key(mid_line+1);
            long long rsum=div_tree.size()-div_tree.order_of_key(rpos);
            long long Rsum=div_tree.size()-div_tree.order_of_key(mid_line);
            if(lpos==-1)
            {
                ans+=Lsum*rsum;
            }
            else if(rpos==-1)
            {
                ans+=lsum*Rsum;
            }
            else
            {
                ans+=lsum*Rsum+Lsum*rsum-lsum*rsum;
            }
            lpos=-1;
            rpos=-1;
        }
    }
    int pin1=l,pin2=r;
    while(p[pin1].x!=mid_line)++pin1;
    while(p[pin2].x!=mid_line)--pin2;
    div_algorithm(l,pin1-1);
    div_algorithm(pin2+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d",&p[i].x,&p[i].y);
    }
    sort(p+1,p+1+n,cmp1);
    div_algorithm(1,n);
    printf("%I64d\n",ans);
    return 0;
}

It is obvious that we can binary search the answer because we can pull any line closer to $$$O$$$ and the situation won't change. Applying a binary search, we focus on if it is possible to set $$$m$$$ barriers with the same distance to $$$O$$$ and meet the requirement. By doing so, we can draw a circle whose center is $$$O$$$ such that the closest point to $$$O$$$ on each barrier is on the circumference. Then it becomes a classic problem — for each barrier we can get the angle range of its closest point on the circle, and we have to choose at most $$$m$$$ points on the circle to ensure that there is at least one point within each range.

This kind of greedy trick is very simple on a sequence. As to ranges on a sequence, you only have to sort all ranges in increasing order of left endpoint and take every necessary right endpoint. As to ranges on a circle, you can enumerate a position to break the circle into a sequence. But if you enumerate as the same way on the sequence, the time complexity will be $$$\mathcal{O}(n^2)$$$ which is not enough.

Instead, we can double and extend these ranges into $$$2 n$$$ ranges and then regard them as on a sequence. We can do some precalculation, such as if we want to choose a point to cover the $$$i$$$-th sorted range and other ranges in its right as many as possible, what is the next range that we cannot cover. Let's denote that as $$$f[i][0]$$$, and then we can calculate the next range after $$$2^p$$$ repeated steps from the $$$i$$$-th range as $$$f[i][p]$$$, which can be obtained from $$$f[f[i][p - 1]][p - 1]$$$. After preparation, we can enumerate the beginning position and use binary lifting method, each time in complexity $$$\mathcal{O}(\log m)$$$, to know that whether we can use $$$m$$$ steps to cover all the ranges.

Therefore, the total time complexity can be $$$\mathcal{O}(n \log m \log D)$$$, where $$$D$$$ is the precision requirement.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define pi acos(-1.0)
#define LOG 20
#define eps 1e-9
 
using namespace std;
const int N = 500010;
const double twopi = 2*acos(-1.0);
int n,m,tot,fa[N*2][LOG];
bool nd[N*2];
double xx[N],yy[N],di[N];
struct Segment
{
    double l,r; bool typ;
    Segment(){}
    Segment(double l,double r,bool typ):l(l),r(r),typ(typ){} 
}q[N*2];
bool cmp(const Segment &a,const Segment &b){ if(a.typ!=b.typ) return a.typ<b.typ; return a.l<b.l; }
bool check(double cur)
{
    tot = 0;
    for(int i=1;i<=n;i++)
    {
        double deg = atan2(yy[i],xx[i]), p = acos(cur/di[i]);
        q[++tot] = Segment(deg-p,deg+p,0);
        q[++tot] = Segment(deg-p+twopi,deg+p+twopi,1);
    }
    sort(q+1,q+1+tot,cmp);
    double mr = 2147483600;
    memset(nd,1,tot+1);
    for(int i=tot;i;i--)
    {
        if(q[i].r>=mr) nd[i] = 0;
        else mr = q[i].r;
    }
    tot = 0;
    for(int i=1;i<=n;i++) if(nd[i]) q[++tot] = q[i];
    for(int i=1;i<=tot;i++) q[i+tot] = Segment(q[i].l+twopi,q[i].r+twopi,1);
    tot <<= 1;
    int j = 1;
    for(int i=1;i<=tot;i++)
    {
        while(j<=tot&&q[i].r>=q[j].l) j++;
        fa[i][0] = j;
    }
    for(int j=1;(1<<j)<=tot;j++)
        for(int i=1;i<=tot;i++)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    for(int i=1;(i<<1)<=tot;i++)
    {
        int p = i, tmp = 0;
        for(int k=m;k;k>>=1,tmp++) 
            if(k&1) p = fa[p][tmp];
        if(p==0||p>=i+(tot>>1)) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    double l = 0, r = 1e100;
    for (int i=1;i<=n;i++) {
        scanf("%lf%lf",&xx[i],&yy[i]);
        di[i] = sqrt(xx[i]*xx[i]+yy[i]*yy[i]);
        r = min(r, di[i]);
    }
    if(m>=n) {
        printf("%.10f\n",r);
        return 0;
    }
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid; else r = mid;
    }
    printf("%.10f\n", l);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN=100005;
const int DEP=18;

vector<pair<int,int> > filter(int n,vector<pair<int,int> > &seg)
{
    vector<pair<int,int> > now;
    for(auto &t:seg)
    {
        t.second=(t.second+n-1)%n;
        int l=t.first,r=t.second;
        if(l<=r)
        {
            now.push_back(make_pair(l,-r));
            now.push_back(make_pair(l+n,-(r+n)));
        }
        else now.push_back(make_pair(l,-(r+n)));
    }
    sort(now.begin(),now.end());
    vector<pair<int,int> > stk;
    for(auto &t:now)
    {
        while(!stk.empty() && stk.back().second<=t.second)
            stk.pop_back();
        stk.push_back(t);
    }
    vector<pair<int,int> > res;
    for(auto &t:stk)if(t.first<n)
        res.push_back(make_pair(t.first,-t.second));
    return res;
}
int go[MAXN<<1][DEP];
int cal(int n,vector<pair<int,int> > &seg)
{
    seg=filter(n,seg);
    int m=(int)seg.size();
    if(m<2)return m;
    for(int i=0;i<m;i++)
    {
        int l=seg[i].first,r=seg[i].second;
        seg.push_back(make_pair(l+n,r+n));
    }
    for(int i=0;i<2*m;i++)
        go[i][0]=lower_bound(seg.begin(),seg.end(),make_pair(seg[i].second+1,0))-seg.begin();
    go[2*m][0]=2*m;
    for(int j=1;j<DEP;j++)
        for(int i=0;i<=2*m;i++)
            go[i][j]=go[go[i][j-1]][j-1];
    int res=m;
    for(int i=0;i<m;i++)
    {
        int t=i,cnt=0;
        for(int j=DEP-1;j>=0;j--)
            if(go[t][j]<i+m)
                t=go[t][j],cnt+=(1<<j);
        if(res>cnt+1)res=cnt+1;
    }
    return res;
}

const db PI=acos(-1.0);
ll x[MAXN],y[MAXN];
db dis[MAXN],ang[MAXN],angl[MAXN],angr[MAXN],anga[MAXN<<1];

bool check(int n,int m,db r)
{
    for(int i=0;i<n;i++)
    {
        db t=acos(min(1.0L,r/dis[i]));
        angl[i]=ang[i]-t,angr[i]=ang[i]+t;
        if(angl[i]<0)angl[i]+=2*PI;
        if(angr[i]>=2*PI)angr[i]-=2*PI;
        anga[i<<1]=angl[i],anga[i<<1|1]=angr[i];
    }
    sort(anga,anga+2*n);
    int k=unique(anga,anga+2*n)-anga;
    vector<pair<int,int> > seg;
    for(int i=0;i<n;i++)
    {
        int l=lower_bound(anga,anga+k,angl[i])-anga;
        int r=lower_bound(anga,anga+k,angr[i])-anga;
        seg.push_back({l,r});
    }
    return cal(k,seg)<=m;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&x[i],&y[i]);
    db md=1e7;
    for(int i=0;i<n;i++)
    {
        dis[i]=sqrtl(x[i]*x[i]+y[i]*y[i]);
        ang[i]=atan2(y[i],x[i]);
        if(ang[i]<0)ang[i]+=2*PI;
        md=min(md,dis[i]);
    }
    if(md<1e-7)return 0*printf("%.12Lf\n",0.0L);
    db tl=0,tr=1;
    while(tr<md && check(n,m,tr))
        tl=tr,tr=min(md,2*tr);
    for(int _=0;_<25;_++)
    {
        db tm=(tl+tr)/2;
        if(check(n,m,tm))tl=tm;
        else tr=tm;
    }
    return 0*printf("%.12Lf\n",(tl+tr)/2);
}

Firstly, let me briefly review this problem for you. Given integers $$$n$$$, $$$m$$$ and $$$p$$$ ($$$n > 0$$$, $$$m > 1$$$, $$$p \neq 0$$$), we denote $$$S = \lbrace x | x \in \mathbb{Z}, 0 \leq x < m, \gcd(m, x) = 1 \rbrace$$$ and $$$T = \lbrace p^e \bmod m | e \in \mathbb{Z}, e \geq 0 \rbrace$$$, where $$$\gcd(m, x)$$$ means the greatest common divisor of $$$m$$$ and $$$x$$$, and you are asked to pick up $$$n$$$ distinct integers from $$$(S - T)$$$, the set of elements in $$$S$$$ but not in $$$T$$$, or report that it is unachievable. Besides, there is an additional restriction, $$$m = q^k$$$ for a prime number $$$q$$$ and a positive integer $$$k$$$.

It is not difficult to show $$$|S|$$$, the size of $$$S$$$, equals to $$$\varphi(m) = m (1 - \frac{1}{q})$$$. When $$$\gcd(m, p) > 1$$$, there is only one element $$$p^0 \bmod m = 1$$$ in $$$T$$$ which is coprime to $$$m$$$, so in that case, $$$|S - T| = \varphi(m) - 1$$$. To output a solution, you can just enumerate the smallest integers and skip the integer $$$1$$$ and any multiples of $$$q$$$. In this process, you won't need to enumerate more than $$$(2 n + 1)$$$ integers, because $$$\frac{n}{1 - \frac{1}{q}} + 1 \leq 2 n + 1$$$.

When $$$\gcd(m, p) = 1$$$, we can observe that $$$T \subseteq S$$$. Let $$$|T|$$$ be $$$\lambda$$$, and we may conclude from Euler's totient theorem that $$$\lambda \leq \varphi(m)$$$, and even $$$\lambda | \varphi(m)$$$. When $$$n > \varphi(m) - \lambda$$$, there is no solution, so we need to calculate $$$\lambda$$$ in order to determine the existence of solutions.

To calculate $$$\lambda$$$, you can just enumerate all the divisors of $$$\varphi(m)$$$ and check them using Fast Power Algorithm, because the number of divisors is not too large due to the restrictions. Alternatively, you can do it more advanced and check more efficiently like the following.

lambda = phi(m)
for each x in prime factors of phi(m) :
	if pow(p, lambda / x, m) == 1 :
		lambda = lambda / x

The above approach requires $$$\mathcal{O}(\log \varphi(m))$$$ calls of Fast Power Algorithm. It is used more regularly when searching a random primitive root in modulo some integer.

When implementing Fast Power Algorithm, you may notice an issue that the modular multiplication may not be easy to code, when the 128-bit integer operations are not directly provided on this platform. In a precise way, you can implement another like Fast Multiplying Algorithm, though it is a bit slow. But if you believe you are lucky enough and you prefer using C/C++, you can try the following code in a convenient way.

typedef long long LL;
typedef long double LD;
LL mod_mul(LL x, LL y, LL mod) { // 0 <= x, y < mod
	LL ret = x * y - (LL)((LD)x * y / mod + 0.5) * mod;
	return ret < 0 ? ret + mod : ret;
}

No matter what approach you used, the factorization of $$$(q - 1)$$$ is inevitable, so the problem requires you to factorize a relatively large number (less than $$$10^{18}$$$) a bit quickly. For example, you can use Pollard's Rho Algorithm with Miller-Rabin Primality Test. By Birthday Paradox, which is a heuristic claim, when $$$x$$$ is not a prime, Pollard's Rho Algorithm can split $$$x$$$ into $$$u \cdot v$$$ in $$$\mathcal{O}(\sqrt{\min(u, v)}) = \mathcal{O}(x^{1 / 4})$$$ iterations. By the way, you can obtain $$$q$$$ from $$$m$$$ by enumerating possible $$$k$$$ from large to small, instead of factorization.

Let's go back to the case that $$$\gcd(m, p) = 1$$$ and $$$n \leq \varphi(m) - \lambda$$$. When any solution exists, we can observe that $$$\varphi(m) - \lambda \geq \frac{\varphi(m)}{2}$$$, so there may exist some solutions based on random distribution. That is, if you are able to check whether an integer is in $$$T$$$ or not, you can roughly pick $$$2 n$$$ integers in $$$S$$$ and check them. One approach is like the mechanism built in the problem checker, but as space is limited, I would not expend it at here. One thing you should be aware of is that you can't pick them without checking, as the probability of failure may be so large, like $$$\frac{1}{2}$$$. Moreover, you can't use Baby-Step-Giant-Step algorithm since its time complexity $$$\mathcal{O}(\sqrt{n m})$$$ is too slow.

If there exists at least one primitive root in modulo $$$m$$$, then we can construct the output integers. Since a primitive root $$$g$$$ can represent $$$S$$$ as $$$\lbrace g^e \bmod m | e \in \mathbb{Z}, 0 \leq e < \varphi(m) \rbrace$$$, we can reduce the problem into something about modular equation that only concerns the exponents. As the number of primitive root in modulo $$$m$$$ is $$$\varphi(\varphi(m))$$$, if the root exists, we can get a random primitive root easily. Now let's assume we find a primitive root $$$g$$$ and $$$p \equiv g^u \pmod{m}$$$. An integer $$$(g^v \bmod m)$$$ is in $$$T$$$ if and only if the equation $$$e u \equiv v \pmod{\varphi(m)}$$$ has a solution of $$$e$$$. It is easy to show, when $$$\gcd(\varphi(m), u) | v$$$, a solution of $$$e$$$ always exists, so the construction is quite straightforward.

The only case we left is when no primitive root exists in modulo $$$m$$$, which occurs when $$$m = 2^k$$$, $$$k \geq 3$$$. In this case, we cannot represent all the elements in $$$S$$$ as non-negative integer powers of one specific number, but we can find a pseudo-primitive root $$$g'$$$ to use its powers to represent all the elements in the form of $$$(4 t + 1)$$$ in $$$S$$$ (as the group $$$(S, \times_m)$$$, also known as $$$(\mathbb{Z}/m\mathbb{Z})^{\times}$$$, is isomorphic to a direct product of cyclic groups, $$$\mathrm{C}_2 \times \mathrm{C}_{2^{k - 2}}$$$). Besides, $$$\lbrace m - ({g'}^{e} \bmod m) | e \in \mathbb{Z}, 0 \leq e < 2^{k - 2} \rbrace$$$ can represent the rest numbers (in the form of $$$(4 t + 3)$$$) in $$$S$$$. As the product of two integers in the form of $$$(4 t + 3)$$$ is in the form of $$$(4 t + 1)$$$, we can discuss the parity of $$$e$$$ in expression $$$(p^e \bmod m)$$$ and check if an integer is in $$$T$$$, so the construction could work after a little modification. By the way, there exist many different construction methods for this case.

In summary, to solve this problem, we need to factorize $$$\varphi(m)$$$, calculate the order of $$$p$$$ in modulo $$$m$$$, find a primitive root $$$g$$$ (or a pseudo-primitive root $$$g'$$$) in modulo $$$m$$$ and enumerate some small integers (values or exponents) to construct a solution.

Time complexity: $$$\mathcal{O}((m^{1 / 4} + n) M(m))$$$, where $$$M(m)$$$ means the cost of one multiplication modulo $$$m$$$. Some slow solutions are accepted as well.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
inline LL mod_add(LL x, LL y, LL mod) {
	return (x += y) < mod ? x : x - mod;
}
inline LL mod_mul(LL x, LL y, LL mod) {
	const int BLEN = __builtin_clzll(mod) - 1;
	const LL BMSK = (1LL << BLEN) - 1;
	LL ret = 0;
	if(x < y)
		swap(x, y);
	while(y > 0) {
		ret += x * (y & BMSK);
		ret = ret < mod ? ret : ret % mod;
		y >>= BLEN;
		x <<= BLEN;
		x = x < mod ? x : x % mod;
	}
	return ret;
/*
	typedef long double LD;
	LL ret = x * y - (LL)((LD)x * y / mod + 0.5) * mod;
	return ret < 0 ? ret + mod : ret;
*/
}
inline LL mod_pow(LL x, LL k, LL mod) {
	LL ret = mod > 1 ? 1 : 0;
	for( ; k > 0; k >>= 1, x = mod_mul(x, x, mod))
		if(k & 1)
			ret = mod_mul(ret, x, mod);
	return ret;
}
inline LL int_pow(LL x, int k, LL upp) {
	LL ret = 1, lim = (++upp) / x;
	for( ; k > 0; --k) {
		if(ret > lim)
			return upp;
		ret *= x;
	}
	return ret;
}
inline bool miller_rabin(LL n) {
	if(n == 2)
		return 1;
	if(n < 2 || !(n & 1))
		return 0;
	LL s, r;
	for(s = 0, r = n - 1; !(r & 1); r >>= 1, ++s);
	static const int ptot = 12, pr[ptot] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
	for(int p : pr) {
		if(p >= n)
			break;
		LL cur = 1, nxt = p;
		for(LL k = r; k > 0; k >>= 1, nxt = mod_mul(nxt, nxt, n))
			if(k & 1)
				cur = mod_mul(cur, nxt, n);
		for(int i = 0; i < s; ++i) {
			nxt = mod_mul(cur, cur, n);
			if(nxt == 1 && cur != 1 && cur != n - 1)
				return 0;
			cur = nxt;
		}
		if(cur != 1)
			return 0;
	}
	return 1;
}
inline LL pollard_rho(LL n) {
	static mt19937_64 rnd(996);
	while(1) {
		LL x = rnd() % (n - 3) + 2, y = x, c = rnd() % n, tim = 0, prd = 1;
		for(LL i = 1, stp = 2; ; ++i) {
			if(i == stp) {
				y = x;
				stp <<= 1;
			}
			if((x = mod_add(mod_mul(x, x, n), c, n)) == y)
				break;
			LL tmp = prd;
			if((prd = mod_mul(prd, abs(y - x), n)) == 0)
				return __gcd(tmp, n);
			static const int maxt = 100;
			if((++tim) < maxt)
				continue;
			if((prd = __gcd(prd, n)) > 1)
				return prd;
			tim = 0;
		}
		if(tim > 0 && (prd = __gcd(prd, n)) > 1)
			return prd;
	}
	assert(0);
}
inline vector<pair<LL, LL> > factorize(LL n) {
	vector<LL> vec;
	queue<LL> que;
	que.push(n);
	while(!que.empty()) {
		LL x = que.front();
		que.pop();
		for(LL y : vec)
			for( ; x % y == 0; x /= y, vec.push_back(y));
		if(x == 1)
			continue;
		if(miller_rabin(x)) {
			vec.push_back(x);
		} else {
			LL y = pollard_rho(x);
			que.push(y);
			que.push(x / y);
		}
	}
	sort(vec.begin(), vec.end());
	vector<pair<LL, LL> > ret;
	for(LL x : vec)
		if(!ret.empty() && ret.back().first == x) {
			++ret.back().second;
		} else {
			ret.push_back(make_pair(x, 1LL));
		}
	return ret;
}

const int maxn = (int)5e5 + 1, maxe = 60;
int n;
LL m, sp, pr, ex, phi, ord, gen;
void init() {
	scanf("%d%lld%lld", &n, &m, &sp);
	for(ex = maxe - 1; ex >= 1; --ex) {
		if(m < (1LL << ex))
			continue;
		LL low = 2, upp;
		for(upp = low << 1; int_pow(upp, ex, m) <= m; upp <<= 1);
		while(low < upp) {
			LL mid = (low + upp + 1) >> 1;
			if(int_pow(mid, ex, m) <= m) {
				low = mid;
			} else {
				upp = mid - 1;
			}
		}
		if(int_pow(low, ex, m) == m) {
			pr = low;
			break;
		}
	}
	assert(ex >= 1 && miller_rabin(pr));
	phi = m - m / pr;
	if(sp % pr == 0) {
		ord = gen = -1;
		return;
	}
	ord = phi;
	vector<pair<LL, LL> > vec = factorize(pr - 1);
	if(ex > 1)
		vec.push_back(make_pair(pr, ex - 1));
	for(pair<LL, LL> it : vec)
		for( ; it.second > 0 && mod_pow(sp, ord / it.first, m) == 1; --it.second, ord /= it.first);
	if(pr == 2 && m >= 8) {
		assert((sp & 3) != 3 || !(ord & 1));
		LL half_phi = phi / 2;
		for(gen = 1; gen < m; gen += 4) {
			bool chk = mod_pow(gen, half_phi, m) == 1;
			for(pair<LL, LL> it : vec)
				chk &= mod_pow(gen, half_phi / it.first, m) != 1;
			if(chk)
				break;
		}
	} else {
		for(gen = 0; gen < m; ++gen) {
			bool chk = mod_pow(gen, phi, m) == 1;
			for(pair<LL, LL> it : vec)
				chk &= mod_pow(gen, phi / it.first, m) != 1;
			if(chk)
				break;
		}
	}
}
void solve() {
	if(n > phi - abs(ord)) {
		puts("-1");
		return;
	}
	if(ord == -1) {
		LL val = 1;
		for(int i = 1; i <= n; ++i) {
			for(++val; val < m && val % pr == 0; ++val);
			assert(val < m);
			printf("%lld%c", val, " \n"[i == n]);
		}
		return;
	}
	if(pr == 2 && m >= 8 && (sp & 3) == 3) {
		LL upp = phi / 2, stp = upp / (ord / 2);
		for(LL e = 0, u = 1, v = sp; e < upp && n > 0; ++e, u = mod_mul(u, gen, m), v = mod_mul(v, gen, m))
			if(e % stp > 0) {
				printf("%lld%c", u, " \n"[!(--n)]);
				if(n > 0)
					printf("%lld%c", v, " \n"[!(--n)]);
			}
	} else {
		LL upp = pr == 2 ? phi / 2 : phi, stp = upp / ord;
		for(LL e = 0, v = 1; e < upp && n > 0; ++e, v = mod_mul(v, gen, m)) {
			if(e % stp > 0)
				printf("%lld%c", v, " \n"[!(--n)]);
			if(n > 0 && pr == 2)
				printf("%lld%c", m - v, " \n"[!(--n)]);
		}
	}
	assert(n == 0);
}
int main() {
	init();
	solve();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline ll mul_mod(ll a, ll b, ll m)
{
    a=(a%m+m)%m,b=(b%m+m)%m;
    return ((a*b-(ll)(1.0L*a/m*b+0.5L)*m)%m+m)%m;
}
inline ll pow_mod(ll a,ll k,ll m)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=mul_mod(res,a,m);
        a=mul_mod(a,a,m);
        k>>=1;
    }
    return res;
}

bool strong_pseudo_primetest(ll n,int b)
{
    ll n2=n-1,res;
    int s=0;
    while(n2%2==0)n2>>=1,s++;
    res=pow_mod(b,n2,n);
    if((res==1)|| (res==n-1))return 1;
    s--;
    while(s>=0)
    {
        res=mul_mod(res,res,n);
        if(res==n-1)return 1;
        s--;
    }
    return 0;
}
bool is_prime(ll n)
{
    static ll testNum[]={2,3,5,7,11,13,17,19,23,29,31,37};
    static ll lim[]={4,0,1373653LL,25326001LL,25000000000LL,2152302898747LL,3474749660383LL,341550071728321LL,0,0,0,0};
    if(n<2 || n==3215031751LL)return 0;
    for(int i=0;i<12;i++)
    {
        if(n<lim[i])return 1;
        if(!strong_pseudo_primetest(n,testNum[i]))return 0;
    }
    return 1;
}

inline ll func(ll x,ll n)
{
    return (mul_mod(x,x,n)+1)%n;
}
ll pollard(ll n)
{
    if(is_prime(n))return n;
    if(~n&1)return 2;
    for(int i=1;i<20;i++)
    {
        ll x=i,y=func(x,n),p=__gcd(y-x,n);
        while(p==1)x=func(x,n),y=func(func(y,n),n),p=__gcd((y-x+n)%n,n)%n;
        if(p==0 || p==n)continue;
        return p;
    }
    return 1;
}
vector<ll> factor(ll n)
{
    if(n==1)return {};
    ll x=pollard(n);
    if(x==n)return {n};
    vector<ll> res=factor(x);
    vector<ll> t=factor(n/x);
    res.insert(res.end(),t.begin(),t.end());
    return res;
}

vector<ll> solve_easy(int n,ll m)
{
    vector<ll> res;
    for(ll i=2;i<m && (int)res.size()<n;i++)
        if(__gcd(i,m)==1)res.push_back(i);
    return res;
}

bool dfs_sol(int i,int k,ull x,ull p,ull t)
{
    if(i>k)return 1;
    ull mask=(1ULL<<i)-1;
    if((t&mask)==(x&mask) && dfs_sol(i+1,k,x,p*p,t))return 1;
    if(((t*p)&mask)==(x&mask) && dfs_sol(i+1,k,x,p*p,t*p))return 1;
    return 0;
}
vector<ll> solve_even(int n,ll m,ll p,int k)///m=2^k
{
    vector<ll> res;
    for(ll i=3;i<m && (int)res.size()<n;i+=2)
        if(!dfs_sol(3,k,i,p,1))res.push_back(i);
    return res;
}

void dfs_fac(int dep,ll val,vector<pair<ll,int> > &pcnt,vector<ll> &fac)
{
    if(dep==(int)pcnt.size())
    {
        fac.push_back(val);
        return;
    }
    for(int i=0;i<=pcnt[dep].second;i++)
    {
        dfs_fac(dep+1,val,pcnt,fac);
        val*=pcnt[dep].first;
    }
}
vector<ll> solve_root(int n,ll m,ll p,vector<ll> pm)
{
    ll phi=m/pm[0]*(pm[0]-1);
    vector<ll> pphi=factor(phi);
    sort(pphi.begin(),pphi.end());
    vector<pair<ll,int> > pcnt;
    for(int i=0,j=0;i<(int)pphi.size();i=j)
    {
        while(j<(int)pphi.size() && pphi[i]==pphi[j])j++;
        pcnt.push_back({pphi[i],j-i});
    }
    pphi.erase(unique(pphi.begin(),pphi.end()),pphi.end());
    vector<ll> fac;
    dfs_fac(0,1,pcnt,fac);
    ll pmr=0;
    while(++pmr)
    {
        bool isok=(__gcd(pmr,m)==1);
        for(int i=0;i<(int)pphi.size() && isok;i++)
            isok&=(pow_mod(pmr,phi/pphi[i],m)>1);
        if(isok)break;
    }
    ll len=phi;
    for(auto &t:fac)
        if(pow_mod(p,t,m)==1)
            len=min(len,t);
    if(len==phi)return {};
    vector<ll> res;
    for(ll i=0;i<phi && (int)res.size()<n;i++)
        if(i%(phi/len))res.push_back(pow_mod(pmr,i,m));
    return res;
}

int main()
{
    int n;
    ll m,p;
    scanf("%d%lld%lld",&n,&m,&p);
    vector<ll> res;
    if(__gcd(m,p)>1)
        res=solve_easy(n,m);
    else
    {
        vector<ll> pm=factor(m);
        if(pm[0]==2 && (int)pm.size()>2)
            res=solve_even(n,m,p,(int)pm.size());
        else
            res=solve_root(n,m,p,pm);
    }
    if((int)res.size()<n)
        printf("-1\n");
    else for(int i=0;i<n;i++)
        printf("%lld%c",res[i]," \n"[i==n-1]);
    return 0;
}