Here's the editorials of TheForces Rounds :
For a number $$$x$$$, as long as $$$2\le x$$$, it can be squared to any large number. For $$$0$$$ and $$$1$$$, the square of both numbers is equal to themselves. So just compare $$$0$$$ and $$$1$$$.
void elysia() {
cin >> n;
bool flag=true;
for(int i=1;i<=n;++i) {
cin >> a[i];
a[i]=min(a[i],2ll);
if(i!=1&&a[i]<a[i-1]) flag=false;
}
if(flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
Consider the number of times each $$$a_i$$$ is XOR in the answer. for $$$a_i$$$, calculated $$$i(n-i+1)$$$ times in the answer. Two same XOR will disappear, so checking is this an odd number then done.
void elysia() {
int answer=0;
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
if(i*(n-i+1)%2==1)
answer^=a[i];
}
cout << answer << endl;
}
$$$\lfloor |\sqrt[K]{N}|\rfloor$$$ is $$$\lfloor\text{exp10}(\frac{\log_{10} N}{K})\rfloor$$$. This is just a simple rounding and division method, you need to pay attention to the even roots of negative numbers.
void elysia() {
string t;
cin >> t >> k;
if(t[0]=='-'&&k%2==0) cout << -1 << endl;
else cout << (t.size()-(t[0]=='-')-1)/k+1 << endl;
}
There are two parts to this problem. The first part is to figure out all the $$$f(a_i!)$$$. , and then calculate the last non-zero digit of the product.
For factorial, only the product of $$$2$$$ and $$$5$$$ factors produces a $$$0$$$ ending. To compute the answer, it's multiplied by $$$2^{cnt_2-cnt_5}$$$.
For the final answer, the same calculation.
int power(int x,int p,int mod) {
int answer=1;
while(p) {
if(p&1)
answer=answer*x%mod;
x=x*x%mod;
p>>=1;
}
return answer;
}
struct num {int x,c2,c5;};
num mul(num a,num b) {
return {a.x*b.x%10,a.c2+b.c2,a.c5+b.c5};
}
int get(num a) {
int t=min(a.c2,a.c5);
a.c2-=t;a.c5-=t;
return a.x*power(2,a.c2,10)*power(5,a.c5,10)%10;
}
num get(int a) {
int c2=0,c5=0;
while(a%2==0) {c2++;a/=2;}
while(a%5==0) {c5++;a/=5;}
return {a,c2,c5};
}
num fac[1000001];
int n,a[1000001];
void elysia() {
cin >> n;
num s={1,0,0};
for(int i=1;i<=n;++i) {
cin >> a[i];
s=mul(s,fac[a[i]]);
}
cout << get(s) << endl;
}
signed main() {
fac[0]={1,0,0};
for(int i=1;i<=1000000;++i)
fac[i]=mul(fac[i-1],get(i));
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
For the product, the only information that is useful is whether $$$a_i$$$ is positive, negative or zero.
So first, the product is equal to $$$0$$$. If one of the numbers in the multiplication is zero, then the result becomes zero. So enumerates zero. To prevent evaluating the same interval more than once, you also need to ensure that the zeros enumerated are the leftmost ones.
So for $$$a_i$$$ if it's zero, and the nearest zero to the left is $$$a_j$$$, then the contribution to the answer is $$$(i-j)(n-i+1)$$$.
Now let's deal with the case where the product is positive. First, the interval cannot cross one or more zeros. So you can split it up from zero into smaller arrays that don't contain zero, and the answer is the sum of those arrays.
If the product of an interval is positive, it must contain an even number of negative numbers. It's same as the sum from $$$l$$$ to $$$r$$$ is even, or $$$\text{sum}(1,r)\equiv\text{sum}(1,l-1)(\text{mod 2})$$$. Then record the parity of the prefix sum, and the problem is solved.
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
int sum0=0,sum1=0;
for(int i=1,l=0;i<=n;++i)
if(a[i]==0) {
sum0+=(i-l)*(n-i+1);
l=i;
}
for(int i=1,even=1,odd=0,prefix=0;i<=n;++i) {
if(a[i]==0) {
even=1;odd=0;prefix=0;
continue;
}
prefix+=a[i]<0;
if(prefix%2==0)
sum1+=even++;
else
sum1+=odd++;
}
cout << sum1 << ' ' << n*(n+1)/2-sum1-sum0 << ' ' << sum0 << endl;
}
The minimum value of $$$n\text{ or }x=n$$$. For every bit of $$$n$$$ equal to $$$1$$$, there are two choices at $$$x$$$, either $$$0$$$ or $$$1$$$. And for bit of $$$n$$$ equals $$$0$$$, we can only choose $$$0$$$ at $$$x$$$. So the answer is power $$$2$$$ of popcount.
void elysia() {
int n;cin >> n;
cout << (1<<__builtin_popcount(n)) << endl;
}
For each $$$a_i$$$, we greedily choose the minimum number of operations that are greater than $$$a_{i+1}$$$, and then determine if the entire array is not decreasing.
Note that the square root in this problem is not rounded down, so if the next number is $$$1$$$, it cannot be reached by the square root alone.
void elysia() {
cin >> n;
for(int i=1;i<=n;++i)
cin >> a[i];
for(int i=n-1;i>=1;--i)
while(a[i]>=2&&a[i]>a[i+1]&&a[i+1]!=1)
a[i]=sqrt(a[i]);
bool flag=true;
for(int i=1;i<n;++i)
flag&=a[i]<=a[i+1];
if(flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
It is easy to notice that the Fibonacci mantissa has a $$$60$$$-length circular section.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
int f[201],n;
void elysia() {
cin >> n;
if(n<=200) cout << f[n] << endl;
else cout << f[n%60+120] << endl;
}
signed main() {
f[1]=1;
for(int i=2;i<=200;++i)
f[i]=(f[i-1]+f[i-2])%10;
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
Consider the case where the product is zero, and to prevent double counting, enumerate the zero again, and then make sure that the zero is the leftmost one.
For a zero, if there are $$$x$$$ non-zero numbers on the left and $$$y$$$ numbers on the right, then the zero to the answer is $$$2^{x+y}$$$.
If the product is negative, only an odd number of negative numbers can be chosen, while positive numbers can be chosen arbitrarily. So enumerate the odd number of choices, and then do the combination number.
void elysia() {
int sum0=0,cntn=0,cntp=0,sum1=0;
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
if(a[i]==0) sum0=(sum0+combi::power(2,cntn+cntp+n-i))%combi::MOD;
cntn+=a[i]<0;
cntp+=a[i]>0;
}
for(int i=1;i<=cntn;i+=2)
sum1=(sum1+combi::power(2,cntp)*combi::C(cntn,i))%combi::MOD;
cout << ((combi::power(2,n)-sum1-sum0-1)%combi::MOD+combi::MOD)%combi::MOD << ' ' << sum1 << ' ' << sum0 << endl;
}
The number of zeros at the end is equal to the minimum of $$$2$$$ and $$$5$$$ factors. It's easy to know that in some factorial, the number of factors of $$$2$$$ is greater than the number of factors of $$$5$$$. So just calculate the number of factors of $$$5$$$. https://codeforces.com/blog/entry/109035#comment-972362
int f(int n) {
int x=n,sum=0,tmp=1;
while(x) {
x/=5;tmp*=5;
sum+=x*(n+1)-tmp*x*(x+1)/2;
}
return sum;
}
void elysia() {
int a,b;
cin >> b >> a;
cout << (f(a)-(b==1?0:f(b-1)))%1000000007 << endl;
}
For every $$$0$$$ bit on $$$n$$$, You can set $$$0$$$ or $$$1$$$, but for each $$$1$$$bit on $$$n$$$, you can only set $$$0$$$.
And since the highest bit of $$$n$$$ is written as $$$0$$$, no matter what I write down in low bit, $$$x$$$ is less than or equal to $$$n$$$. So the answer is $$$2^{\text{cnt0}}$$$.
void elysia() {
int n;cin >> n;
cout << (n==0?1:(1<<(__lg(n)-__builtin_popcount(n)+1))) << endl;
}
Calculate the xor sum of the all array, and then take advantage of the fact that two same numbers cancel out.
void elysia() {
cin >> n >> q;
int s=0;
for(int i=1;i<=n;++i) {
cin >> a[i];
s^=a[i];
}
for(int i=1,x,y;i<=q;++i) {
cin >> x >> y;
s^=a[x];
a[x]|=y;
s^=a[x];
cout << s << endl;
}
}
Obviously $$$k=x^x$$$ meets the above three conditions.
int power(int x,int p,int mod) {
int answer=1;
while(p) {
if(p&1)
answer=answer*x%mod;
x=x*x%mod;
p>>=1;
}
return answer;
}
void elysia() {
int x;cin >> x;
cout << power(x,x,1000000007) << endl;
}
Direct brute force compare and remove string will TLE, so optimization it.
Scan the entire string from left to right, removing the last matching characters if the last paragraph matches $$$t$$$. This is going to be $$$\Theta(|s||t|)$$$, can get pass it.
void elysia() {
string s,t,q;
cin >> s >> t;
int sum=0;
for(int i=0;i<(int)s.size();++i) {
q.push_back(s[i]);
while(q.size()>=t.size()) {
bool flag=true;
for(int j=0;j<(int)t.size();++j)
if(q[q.size()-t.size()+j]!=t[j])
flag=false;
if(flag) {
for(int j=0;j<(int)t.size();++j)
q.pop_back();
sum++;
}
else
break;
}
}
cout << (sum%2==0?"Bob":"Alice") << endl;
}
If I want to use $$$a$$$ to operate one, I can split it up into $$$a$$$ ones to do the same thing with same score.
We then use dp, assuming $$$dp_i$$$ is the shortest distance from $$$1$$$ to $$$i$$$, so we can operate $$$2$$$ by enumerating all the factors of $$$i$$$. The total number of factors from $$$1$$$ to $$$n$$$ is $$$\Theta(n\ln n)$$$, so it can pass.
The point to note is that preprocessing all factors leads to MLE. You have to compute the factors one time and do dp one time, so that the memory is $$$\Theta(n)$$$, not $$$\Theta(n\ln n)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
int dp[1000001];
void elysia() {
int n;cin >> n;
cout << dp[n] << endl;
}
signed main() {
dp[1]=0;
for(int i=2;i<=1000000;++i) dp[i]=2147483647;
for(int i=2;i<=1000000;++i) {
dp[i]=min(dp[i],dp[i-1]+1);
for(int j=i*2;j<=1000000;j+=i)
dp[j]=min(dp[j],dp[i]+j/i);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
The factor contained in $$$n!$$$, must be $$$\le n$$$, So the answer is at least the closest prime number to $$$n$$$. Otherwise you can't get that prime factor.
I can't prove it. But this can pass.
int cmp(int a,int b) {
return a>b;
}
void elysia() {
int n;cin >> n;
if(n<=4) cout << vector<int>{0,0,2,3,4}[n] << endl;
else cout << *lower_bound(Fact::Prime.rbegin(),Fact::Prime.rend(),n,cmp) << endl;
}
signed main() {
Fact::init(1000000);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
google "Cantor expansion".
void elysia() {
int sum=0;
cin >> n;
for(int i=n;i>=1;--i) {
cin >> a[i];
c[i]=0;
}
for(int i=1,fac=1,s,j;i<=n;++i) {
for(s=0,j=a[i];j!=0;j-=j&-j) s+=c[j];
sum=(sum+fac*s)%1000000007;
fac=fac*i%1000000007;
for(int j=a[i];j<=n;j+=j&-j) ++c[j];
}
cout << sum << endl;
}
Enumerate $$$k$$$ and $$$p$$$, and then we get an upper bound on $$$a_ia_j$$$. You can use any log data structure to maintain it. I used discretization and fenwick tree in the code.
void elysia() {
cin >> n >> x;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=0;i<=n*n;++i) c[i]=0;
vector<int> Q;
for(int i=1;i<=n;++i) {
for(int j=i+1;j<=n;++j)
Q.push_back(x/(a[i]*a[j]));
for(int j=1;j<i;++j)
Q.push_back(a[i]*a[j]);
}
sort(Q.begin(),Q.end());
Q.resize(unique(Q.begin(),Q.end())-Q.begin());
int ans=0;
for(int i=1;i<=n;++i) {
for(int j=i+1;j<=n;++j) {
int t=lower_bound(Q.begin(),Q.end(),x/(a[i]*a[j]))-Q.begin()+1;
for(;t!=0;t-=t&-t) ans+=c[t];
}
for(int j=1;j<i;++j) {
int t=lower_bound(Q.begin(),Q.end(),a[i]*a[j])-Q.begin()+1;
for(;t<=n*n;t+=t&-t) ++c[t];
}
}
cout << ans << endl;
}
Because $$$a\text{ and }b\le\max(a,b)$$$, so all integer pairs satisfy the condition.
void elysia() {
int n;cin >> n;
cout << (int)((__int128(n+1)*(n+2)/2)%998244353) << endl;
}
$$$\sqrt[n]{x_1·x_2·...·x_n}=e^{\frac{\sum_i\ln x_i}{n}}$$$
So the smallest $$$x_i$$$ is the result.
void elysia() {
int n,x=1000000001;
cin >> n;
for(int i=1,t;i<=n;++i) {
cin >> t;x=min(x,t);
}
cout << x << endl;
}
Because we can rearrange all elements, we can greedily put all satisfaction pairs last. Then the problem becomes maximizing the number of satisfied pairs. Sort first, and then find the minimum $$$b$$$ that meets the condition for each $$$a$$$.
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=n;++i) cin >> b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int sum=0,res=0;
for(int i=1,p=1;i<=n;++i) {
while(p!=n+1&&b[p]<a[i]) p++;
if(p==n+1) break;
p++;sum++;
}
for(int i=n;i>=n-sum+1;--i)
res+=i;
cout << res << endl;
}
Because if the sums are the same, the smaller the difference, the larger the product. So put $$$9$$$ as far ahead as possible, until the sum of the numbers is not enough, and put two numbers as close as possible. Then calculate the product.
void elysia() {
int n,s,a=0,b=0;
cin >> n >> s;
if(n==1&&s<2) {
cout << 0 << endl;
return;
}
if(s<2||s>18*n) {
cout << -1 << endl;
return;
}
for(int i=1;i<=n;++i) {
int t=min(s,18ll);
a=(a*10+t/2)%998244353;
b=(b*10+t/2+t%2)%998244353;
s-=t;
}
cout << a*b%998244353 << endl;
}
The classic inclusion-exclusion-principle question. Enumerates whether the number to be calculated is divisible or not for all a_i, and then performs the calculation. It's $$$\Theta(2^n)$$$.
Remember to watch out for long long overflows.
#define int __int128
int a[20],n,s,l,r;
int gcd(int a,int b) {
if(b==0) return a;
return gcd(b,a%b);
}
int lcm(int a,int b) {
return a*b/gcd(a,b);
}
void elysia() {
long long _n,_l,_r;
cin >> _n >> _l >> _r;
n=_n;l=_l;r=_r;
int sum=0;
for(signed i=0;i<n;++i) {
long long t;
cin >> t;
a[i]=t;
}
for(signed i=1;i<(1<<n);++i) {
bool flag=true;
int c=1;
for(signed j=0;j<n;++j)
if((i>>j)%2==1) {
c=lcm(c,a[j]);
if(c>r) {
flag=false;
break;
}
}
if(flag) {
if(__builtin_popcount(i)%2==1)
sum+=r/c-(l-1)/c;
else
sum-=r/c-(l-1)/c;
}
}
cout << (long long)sum << endl;
}
The black ball is first separated by the $$$n-1$$$ white ball to prevent the black ball from being merged. You will then find that the remaining white balls can be placed at random, which can be easily calculated using the combination numbers.
Next calculate the black balls. It is equal to the product of $$$n!$$$ divided by the factorial of all the same number of black balls. Because black balls of the same length are indistinguishable.
Done.
void elysia() {
int n,m;
cin >> n >> m;
map<int,int> Q;
for(int i=1,x;i<=n;++i) {
cin >> x;
Q[x]++;
}
int s=combi::C(m+1,n)*combi::fac[n]%998244353;
for(auto i:Q) s=s*combi::finv[i.second]%998244353;
cout << s << endl;
}
Scan from left to right and fill each pending position greedily with the minimum value.
It is easy to get to $$$\Theta(n\log n)$$$ using set, but there is actually a $$$\Theta(n)$$$ two pointer approach here.
void elysia() {
set<int> Q;
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
Q.insert(i);
}
for(int i=1;i<=n;++i)
Q.erase(a[i]);
for(int i=1;i<=n;++i)
if(a[i]!=0)
cout << a[i] << ' ';
else {
cout << *Q.begin() << ' ';
Q.erase(Q.begin());
}
cout << endl;
}
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
vis[i]=false;
}
for(int i=1;i<=n;++i) vis[a[i]]=true;
for(int i=1,pt=1;i<=n;++i)
if(a[i]!=0)
cout << a[i] << ' ';
else {
while(vis[pt]) pt++;
cout << pt << ' ';
vis[pt]=true;
}
cout << endl;
}
If there is an $$$a_i$$$ that is odd, then we can reach the goal in at most one step, regardless of whether the sum is even or odd.
Otherwise keep performing one operation until we satisfy that there is an $$$a_i$$$ that is odd.
void elysia() {
int s=0,m=2147483647;
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
s+=a[i];
m=min(m,a[i]&-a[i]);
}
cout << __lg(m)+(s/m%2==0) << endl;
}
Greed problem.
First sort $$$a$$$, then the least costly construction is two adjacent connections.
and the most costly construction is Link the two furthest ones first, and subsequently let all nodes link to the one that is further away from these two furthest nodes.
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
sort(a+1,a+1+n);
int s=0;
for(int i=2;i<n;++i)
s+=max(a[n]-a[i],a[i]-a[1]);
cout << a[n]-a[1] << ' ' << s+a[n]-a[1] << endl;
}
Essentially, this question is a count of slopes, since for points of the same slope we can only keep the one closest to the origin.
The special judgement required is whether there is a $$$(0,0)$$$ point, because if there is, we will never be able to draw another pure line.
int gcd(int a,int b) {
if(a<b) swap(a,b);
if(b==0) return a;
return gcd(b,a%b);
}
void elysia() {
set<pair<int,int>> Q;
cin >> n;
bool flag=false;
for(int i=1,a,b;i<=n;++i) {
cin >> a >> b;
int t=gcd(abs(a),abs(b));
if(t==0) flag=true;
else {
a/=t;b/=t;
}
Q.insert({a,b});
}
cout << (flag?1:Q.size()) << endl;
}
In an array, only the last two numbers matter. So we set up a dp.
state $$$dp_{i,j,k}$$$ represents the number of conditional arrays of length $$$i$$$ and the last two digits of $$$j$$$ and $$$k$$$.
Transfer equation is $$$dp_{I,J,K}=\sum\limits_{i=max(1,J-k)}^{min(n,J+k)}dp_{I-1,i,J}$$$
But this is $$$\Theta(n^4)$$$, which gives you TLE. So we take a prefix and optimize it in the second dimension, turning it into $$$\Theta(n^3)$$$, add a rolling dp optimization, then can pass.
If you didn't use a rolling dp optimization, the space would be $$$\Theta(n^3)$$$ instead of $$$\Theta(n^2)$$$, which would give you MLE.
void elysia() {
cin >> n >> k;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dp[0][i][j]=i;
for(int i=1;i<=n-2;++i) {
for(int j=0;j<=n;++j)
for(int l=0;l<=n;++l)
dp[i%2][j][l]=0;
for(int l=1;l<=n;++l)
for(int j=1;j<=n;++j)
dp[i%2][j][l]=(dp[i%2][j-1][l]+dp[(i+1)%2][min(min(j,l)+k,n)][j]-dp[(i+1)%2][max(max(j,l)-k,1ll)-1][j])%998244353;
}
int s=0;
for(int i=1;i<=n;++i)
s+=dp[n%2][min(i+k,n)][i]-dp[n%2][max(i-k,1ll)-1][i];
cout << (s%998244353+998244353)%998244353 << endl;
}
Monotonic stack optimization dp.
First we design the dp state. $$$dp_i$$$ denotes the minimum number of steps required to reach $$$i$$$. At the same time we also want to maintain the minimum $$$s_i$$$ needed to get there.
In line with greed, if there were multiple identical dp values available for me to transfer, I would choose the dp closest to me.
this would keep my $$$s_i$$$ to a minimum and allow for more options to be generated for the next transfer.
This means that if there is a dp value that is far away from me and the value is not good enough, then that dp value can be removed.
We can maintain it with a monotonic stack and do a binary search every time. It's $$$O(n\log n)$$$.
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
s[i]=s[i-1]+a[i];
}
vector<pair<int,int>> ms={{0,0}};
for(int i=1;i<=n;++i) {
if(a[i]>=s[i-1])
dp[i]=a[i];
else
dp[i]=s[i]-s[(*lower_bound(ms.rbegin(),ms.rend(),pair<int,int>{s[i],2147483647},greater<pair<int,int>>())).second];
while(!ms.empty()&&(*ms.rbegin()).first>=dp[i]+s[i])
ms.pop_back();
ms.push_back({dp[i]+s[i],i});
cout << dp[i] << ' ';
}
cout << endl;
}
Do it by hand below $$$10$$$ and you'll see the pattern, and maybe you can only prove it by mathematical induction.
void elysia() {
int n;cin >> n;
cout << (n%3==0?"Urvik":"Dhruv") << endl;
}
The answer is first discussed in a binary serach, and then all possible substrings are enumerated according to the answer, using dp for each substring.
The dp state is $$$dp_{i,j}$$$, currently up to $$$i$$$, and my last number is $$$j$$$, the minimum number of operations used.
The complexity is $$$\Theta(n^2\log n)$$$.
int n,k,dp[1001][4];
string s;
bool check(int x) {
for(int i=0;i<=n-x;++i) {
string t;
for(int j=i;j<i+x;++j)
t.push_back(s[j]);
for(int i=0;i<4;++i)
dp[0][i]=(t[0]!='0'+i);
for(int i=1;i<x;++i) {
for(int j=0;j<4;++j) {
dp[i][j]=2147483647;
for(int k=0;k<=j;++k)
dp[i][j]=min(dp[i][j],dp[i-1][k]);
dp[i][j]+=t[i]!='0'+j;
}
}
if(min({dp[x-1][0],dp[x-1][1],dp[x-1][2],dp[x-1][3]})<=k)
return true;
}
return false;
}
void elysia() {
cin >> n >> k >> s;
for(int i=0;i<n;++i)
s[i]=(s[i]=='7'?'0':s[i]=='4'?'1':s[i]=='8'?'2':'3');
int l=1,r=n,m,answer=0;
while(l<=r) {
m=(l+r)/2;
if(check(m)) {
answer=m;l=m+1;
} else r=m-1;
}
cout << answer << endl;
}
This is a hard version of question B.
Noting that dp in Problem B can be described as a multiplication of multiple matrices, it is sufficient to use a segment tree with two pointers to maintain the matrix.
For a node $$$[l,r]$$$ that maintains sixteen dp values, $$$[l,r].dp_{\text{i,j}}$$$ represents the minimum number of operations required to start with $$$i$$$ and end with $$$j$$$.
struct node{
int s11,s12,s13,s14,s22,s23,s24,s33,s34,s44;
node(){
s11=s12=s13=s14=s22=s23=s24=s33=s34=s44=0;
}
};
node get(int x) {
node answer;
answer.s11=answer.s22=answer.s33=answer.s44=1;
if(x==1) answer.s11=0;
if(x==2) answer.s22=0;
if(x==3) answer.s33=0;
if(x==4) answer.s44=0;
answer.s12=answer.s13=answer.s14=answer.s23=answer.s24=answer.s34=2147483647;
return answer;
}
node merge(node x,node y) {
node answer;
answer.s11=x.s11+y.s11;
answer.s12=min({x.s11+y.s12,x.s12+y.s22,x.s11+y.s22});
answer.s13=min({x.s11+y.s13,x.s12+y.s23,x.s13+y.s33,x.s11+y.s23,x.s12+y.s33,x.s11+y.s33});
answer.s14=min({x.s11+y.s14,x.s12+y.s24,x.s13+y.s34,x.s14+y.s44,x.s11+y.s24,x.s12+y.s34,x.s13+y.s44,x.s11+y.s44,x.s11+y.s34,x.s12+y.s44});
answer.s22=x.s22+y.s22;
answer.s23=min({x.s22+y.s23,x.s23+y.s33,x.s22+y.s33});
answer.s24=min({x.s22+y.s24,x.s23+y.s34,x.s24+y.s44,x.s22+y.s34,x.s23+y.s44,x.s22+y.s44});
answer.s33=x.s33+y.s33;
answer.s34=min({x.s33+y.s34,x.s34+y.s44,x.s33+y.s44});
answer.s44=x.s44+y.s44;
return answer;
}
This is a 2d dsu problem. Simply sort first, scan from smallest to largest, add the resulting nodes to the set, and determine if it has only one connected block.
void solve() {
std::vector<int> a, b, fa;
std::set<int> P;
std::cin >> n;
a.resize(n);
b.resize(n);
fa.resize(n);
for(int i = 0; i < n; i++) {
std::cin >> b[i];
b[i]--;
a[i] = -1;
if(b[i] == i)
P.insert(i);
fa[i] = i;
}
auto getfa = [&](auto getfa, int x, std::vector<int> &fa) -> int {
if(x == fa[x]) return x;
return fa[x] = getfa(getfa, fa[x], fa);
};
for(int i = 0; i < n - 1; i++) {
if(P.empty()) {
std::cout << "-1\n";
return;
}
a[i] = *P.begin();
P.erase(P.begin());
fa[getfa(getfa, a[i], fa)]=(getfa(getfa, a[i], fa) + 1) % n;
if(getfa(getfa, b[getfa(getfa, a[i], fa)], fa)==getfa(getfa, a[i], fa))
P.insert(b[getfa(getfa, a[i], fa)]);
}
for(int i = 0; i < n; i++)
std::cout << (a[i] == -1 ? *P.begin() + 1 : a[i] + 1) << ' ';
std::cout << '\n';
}
Start by doing the sorting first, then use as many two-operations as possible. This is because the two-operation removes one more number and satisfies the greed principle.
void elysia() {
cin >> n;
vector<int> Q;
for(int i=1,x;i<=n;++i) {
cin >> x;
Q.push_back(x);
}
int s=0;
sort(Q.begin(),Q.end());
while(!Q.empty()) {
if(Q.size()>=2&&Q.end()[-1]-Q.end()[-2]<=2) {
Q.pop_back();
Q.pop_back();
} else Q.pop_back();
s++;
}
cout << s << endl;
}
Clearly $$$6n$$$ has three factors, $$$1n+2n+3n=6n$$$.
void elysia() {
cin >> n;
cout << 6*n << ' ' << 3 << endl;
cout << n << ' ' << n*2 << ' ' << n*3 << endl;
}
Use dp. $$$dp_{\text{i,j}}$$$ indicates the maximum number of coins that can be obtained when $$$(i,j)$$$ is reached. done
void elysia() {
cin >> n;
for(int i=1;i<=n;++i) {
cin >> s;
for(int j=0;j<3;++j)
if(s[j]!='*')
for(int k=-1;k<=1;++k)
if(k+j>=0&&k+j<3)
dp[i][j]=max(dp[i][j],dp[i-1][j+k]+(s[j]=='c'));
}
cout << max({dp[n][0],dp[n][1],dp[n][2]}) << endl;
}
The first step is to transform $$$px=qy$$$ to $$$0=qy-px$$$. In one operation we can add both $$$x$$$ and $$$y$$$ by one, meaning that we can increase the value on the right by $$$(q-p)$$$.
So the answer is the value on the right divided by the value decreasing each time.
void elysia() {
int p,q,x,y,s;
cin >> p >> q >> x >> y;
s=q*y-p*x;
if(p==q)
cout << (x==y?0:-1) << endl;
else
if(s%(p-q)!=0||s*(p-q)<0)
cout << -1 << endl;
else
cout << s/(p-q) << endl;
}
Maintain at each $$$(i,i)$$$ the number of apples we might be able to get, and then do meet-in-middle.
int n,m,k,s,a[22][22],ans;
map<int,int> P[21];
void dfs1(int x,int y,int t) {
t%=k;
if(x>n||y>m) return;
if(x+y==n+1) {
P[x][t%k]++;
return;
}
dfs1(x+1,y,t+a[x+1][y]);
dfs1(x,y+1,t+a[x][y+1]);
}
void dfs2(int x,int y,int t) {
t%=k;
if(x<0||y<0) return;
if(x+y==n+1) {
ans+=P[x][(k-t%k)%k];
return;
}
dfs2(x-1,y,t+a[x][y]);
dfs2(x,y-1,t+a[x][y]);
}
void elysia() {
cin >> n >> m >> k;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin >> a[i][j];
dfs1(1,1,a[1][1]);
dfs2(n,m,0);
cout << ans << endl;
}
We enumerate the position of the middlemost value and then make a greedy selection of the two sides.
Consider maintaining two arrays lmax[i] and rmax[i].
lmax[i] denotes the longest identical value from $$$1$$$ to $$$i$$$, while rmax[i] denotes the longest identical value from $$$i$$$ to $$$n$$$. Then simply merge.
int n,lmax[100001],rmax[100001],a[100001];
vector<int> P[100001];
void elysia() {
cin >> n;
vector<int> Q;
for(int i=1;i<=n;++i) {
cin >> a[i];
Q.push_back(a[i]);
P[i].clear();
lmax[i]=rmax[i]=0;
}
sort(Q.begin(),Q.end());
Q.resize(unique(Q.begin(),Q.end())-Q.begin());
for(int i=1;i<=n;++i) {
a[i]=lower_bound(Q.begin(),Q.end(),a[i])-Q.begin()+1;
P[a[i]].push_back(i);
}
for(int i=1;i<=n;++i) {
for(int j=0;j<(int)P[i].size();++j)
lmax[P[i][j]]=max(lmax[P[i][j]],j+1);
for(int j=0;j<(int)P[i].size();++j)
rmax[P[i][j]]=max(rmax[P[i][j]],(int)P[i].size()-j);
}
for(int i=2;i<=n;++i)
lmax[i]=max(lmax[i],lmax[i-1]);
for(int i=n-1;i>=1;--i)
rmax[i]=max(rmax[i],rmax[i+1]);
int answer=0;
for(int i=0;i<n;++i)
answer=max(answer,min(lmax[i],rmax[i+1])*2);
cout << answer << endl;
}
This is not a regular CP round so I have not written this.
According to the principle of greed, we always put books with fewer pages at the top of the list to read.
void elysia() {
cin >> n >> m;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=m;++i) cin >> b[i];
sort(b+1,b+1+m);
b[m+1]=1000000000000000000;
for(int i=1,j=1,s=0;i<=n;++i) {
s+=a[i];
while(s>=b[j]) {
s-=b[j];j++;
}
cout << j-1 << ' ';
}
cout << endl;
}
Enumerate $$$a$$$ and $$$b$$$, then save them as arrays and simply output them for each query.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
int c[10000001],n;
void elysia() {
cin >> n;
cout << c[n] << endl;
}
signed main() {
for(int i=0;i<=3200;++i)
for(int j=0;j<=3200;++j)
if(i*i+j*j<=10000000)
c[i*i+j*j]=1;
for(int i=1;i<=10000000;++i)
c[i]+=c[i-1];
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
Decrease $$$n$$$ to the nearest lucky number and calculate it as $$$4$$$ and $$$7$$$ in binary.
This requires some sort of discussion.
tbh I don't know how to write an editorial on this type of problem.
void elysia() {
cin >> s;
reverse(s.begin(),s.end());
if(s.end()[-1]<'4') {
s.pop_back();
if(s.size()==0) {
cout << 0 << endl;
return;
}
s.end()[-1]='9';
}
reverse(s.begin(),s.end());
int sum=power(2,s.size(),998244353)-2;
for(int i=0;i<(int)s.size();++i) {
if(s[i]<'4') break;
if(s[i]>'4'&&s[i]<'7') {
sum+=power(2,s.size()-i-1,998244353);
break;
}
if(s[i]=='7')
sum+=power(2,s.size()-i-1,998244353);
if(s[i]>'7') {
sum+=power(2,s.size()-i,998244353);
break;
}
if(i==(int)s.size()-1) sum++;
}
cout << (sum+998244353)%998244353 << endl;
}
For good subarrays, just use two-pointer to solve it, while for good subsequences, sort first and then do two-pointer.
To prevent double counting, for a fixed $$$l$$$, the contribution of the subarray is $$$r-l+1$$$ and the contribution of the subsequence is $$$2^{r-l}$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
int n,k,a[200001],pw2[200001];
class STT {
private:
typedef pair<int,int> node;
vector<node> mx[22];
public:
node merge(node &a,node &b){return {max(a.first,b.first),min(a.second,b.second)};}
void init(vector<node> x){for(int i=0;i<=21;++i) mx[i].resize(x.size()+1);for(int i=0;i<(int)x.size();++i)mx[0][i+1]=x[i];for(int j=1;j<=21;++j)for(int i=1;i+(1<<j)-1<=(int)x.size();++i)mx[j][i]=merge(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);}
node Query(int l,int r){int k=log2(r-l+1);return merge(mx[k][l+1],mx[k][r-(1<<k)+2]);}
};
int t(pair<int,int> x){return x.first-x.second;}
void elysia() {
cin >> n >> k;
for(int i=1;i<=n;++i) cin >> a[i];
STT b;vector<pair<int,int>> Q={{0,0}};
for(int i=1;i<=n;++i) Q.push_back({a[i],a[i]});
b.init(Q);
int sum1=0,sum2=0;
for(int l=1,r=1;l<=n;++l) {
while(r!=n&&t(b.Query(l,r+1))<=k) r++;
sum1+=r-l+1;
}
sort(a+1,a+1+n);
for(int l=1,r=1;l<=n;++l) {
while(r!=n&&a[r+1]-a[l]<=k) r++;
sum2+=pw2[r-l];
}
cout << sum1%998244353 << ' ' << sum2%998244353 << endl;
}
signed elysia() {
pw2[0]=1;
for(int i=1;i<=200000;++i)
pw2[i]=pw2[i-1]*2%998244353;
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) elysia();
}
It is easy to notice that the Fibonacci mantissa has a $$$75$$$-length circular section.
void elysia() {
int n;
cin >> n;
if(n<=2) cout << vector<int>{0,1,2}[n] << endl;
else cout << vector<int>{6,7,2,8,9,0,6,1,2,8,9,0,0,1,2,8,9,4,0,1,2,8,3,4,0,1,2,2,3,4,0,1,6,2,3,4,0,5,6,2,3,4,4,5,6,2,3,8,4,5,6,2,7,8,4,5,6,6,7,8,4,5,0,6,7,8,4,9,0,6,7,8,8,9,0}[(n-3)%75] << endl;
}
F(n)=(A130665(n)+n+1)/2
unordered_map<int,int> Q;
int calc(int n) {
if(n==0) return 1;
if(Q.count(n)) return Q[n];
if(n%2==1) return Q[n]=4*calc(n/2);
return Q[n]=3*calc(n/2-1)+calc(n/2);
}
void elysia() {
int n;
cin >> n;
cout << (calc(n)+n+1)/2 << endl;
}
If we want to skip intervals with a length exceeding 1, we can do so by continuously skipping intervals with a length of 1 without causing any losses. For skipping a 1-length interval, its impact on the answer is -1, so choose to skip or select each number greedily.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
void Delta() {
int n,s=0;cin >> n;
for(int i=1,x;i<=n;++i) {
cin >> x;
s+=max(-1ll,x);
}
cout << s << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
let $$$b_i=a_i-i$$$, then the problem became the sum of $$$|b_i-x|$$$. For this problem, we can choose the median of the b array.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
void Delta() {
int n,s=0;cin >> n;
vector<int> a(n+1);
for(int i=1;i<=n;++i) {
cin >> a[i];
a[i]-=i;
}
sort(a.begin()+1,a.end());
for(int i=1;i<=n;++i)
s+=abs(a[a.size()/2]-a[i]);
cout << s << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
By using time as the dimension of a two-dimensional array, it can be observed that a[i][j]=a[i-1][j]+a[i][j-1]. This leads to the Pascal triangle, so the answer is the combination number.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace combi {
long long MOD;
vector<long long> fac,inv,finv;
long long C(long long x,long long y){if(x<0||y>x)return(0);return(fac[x]*finv[y]%MOD*finv[x-y]%MOD);}
long long power(long long b,long long n){b%=MOD;long long s=1;while(n){if(n%2==1)s=s*b%MOD;b=b*b%MOD;n/=2;}return s;}
void init(int n,long long mod){fac.resize(n+1);inv.resize(n+1);finv.resize(n+1);MOD=mod;fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1;for(long long i=1;i<=n;++i)fac[i]=fac[i-1]*i%MOD;for(long long i=2;i<=n;++i)inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;for(long long i=2;i<=n;++i)finv[i]=finv[i-1]*inv[i]%MOD;}
void init(long long mod){init(1000010,mod);}
long long Inv(int x){return power(x,MOD-2);}
};
#define int long long
const int MOD=1e9+7;
void Delta() {
int n,k;cin >> n >> k;
cout << combi::C(n+k-1,k) << endl;
}
signed main() {
combi::init(200001,MOD);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
In $$$[1,10^{18}]$$$,there's only $$$10^6$$$ different $$$\lfloor\sqrt[3]{x}\rfloor$$$.
Therefore, we can preprocess all $$$10^6$$$ numbers and their results, and then use the prefix sum for calculation.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
int pw3[1000010],pre[1000010];
int calc(int x) {
if(x==0) return 0;
int cb3=lower_bound(pw3,pw3+1000003,x)-pw3;
return pre[cb3-1]+x/cb3-pw3[cb3-1]/cb3;
}
void Delta() {
int l,r;cin >> l >> r;
cout << calc(r)-calc(l-1) << endl;
}
signed main() {
for(int i=1;i<=1000007;++i) {
pw3[i]=(i+1)*(i+1)*(i+1)-1;
pre[i]=pw3[i]/i-(i*i*i-1)/i+pre[i-1];
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
Consider bit mask dp, transfer from top to bottom.
we make dp[bitmask][i] = the number of possible solutions for the i-th line bitmask
In order to prevent the occurrence of two adjacent 1s, we need to ensure that there are no two adjacent 1s in the binary of the bitmask, and that the bit-and value of the two bitmasks during the transition must also be zero.
assuming that the two bitmasks transferred are a and b, then we have a&b=0, It can be obtained that a is a subset of ~b(Flip each bit of b), Then we can first perform SOS-DP, obtain the answer, and reverse it.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
// #define int long long
long long power(long long x,long long p,long long mod) {
long long answer=1;x%=mod;
while(p) {
if(p&1)
answer=answer*x%mod;
x=x*x%mod;
p>>=1;
}
return answer;
}
const int MOD=998244353;
char a[15][15];
int n,m,ok[32768],dp[32768][2],s,cnt;
void Delta() {
cin >> n >> m;
for(int i=0;i<(1<<max(n,m));++i) {
ok[i]=true;
for(int j=0;j<max(n,m);++j)
if((i>>j)%4==3)
ok[i]=false;
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) {
cin >> a[i][j];
cnt+=a[i][j]=='?';
}
for(int i=0;i<(1<<m);++i) dp[i][0]=ok[i];
for(int i=0;i<m;++i)
if(a[0][i]!='?')
for(int j=0;j<(1<<m);++j)
if((j>>i)%2!=a[0][i]-'0')
dp[j][0]=0;
for(int i=1;i<n;++i) {
for(int j=0;j<(1<<m);++j) dp[j][i%2]=dp[j][(i-1)%2];
for(int j=0;j<m;++j)
for(int k=0;k<(1<<m);++k)
if(k&(1<<j))
dp[k][i%2]=(dp[k][i%2]+dp[k^(1<<j)][i%2])%MOD;
for(int j=0;j<(1<<(m-1));++j)
swap(dp[j][i%2],dp[(1<<m)-j-1][i%2]);
for(int j=0;j<m;++j)
if(a[i][j]!='?')
for(int k=0;k<(1<<m);++k)
if((k>>j)%2!=a[i][j]-'0')
dp[k][i%2]=0;
for(int j=0;j<(1<<m);++j)
if(!ok[j])
dp[j][i%2]=0;
}
for(int i=0;i<(1<<m);++i)
s=(s+dp[i][(n-1)%2])%MOD;
cout << power(499122177,cnt,MOD)*s%MOD << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
I'm sorry to let $$$\Theta(n^3)$$$ brute force pass.
Consider the contribution of a pair to the answer.
(i,j) is counted in the answer if and only if the number of selected numbers from 1 to i-1 is equal to the number of selected numbers from j+1 to n.
so it's $$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n2^{j-i+1}\sum\limits_{x=0}^{n}\text{C}(i-1,x)\text{C}(n-j,x)$$$
we know $$$\text{C}(n-j-1,x)=\text{C}(n-j-1,n-j-1-x)$$$, so we actually selected $$$x$$$ numbers in $$$[1,i-1]$$$ and $$$n-j-x$$$ numbers in $$$[j+1,n]$$$.
$$$x$$$ is in the range of $$$0$$$ to $$$n$$$, so any $$$x$$$ is ok, and a total of $$$n-j$$$ numbers were selected, so the answer to this sum equation is $$$\text{C}(n+i-j-1,n-j)$$$.
By replacing this result, we can get the answer in $$$\Theta(n^2)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace combi {
long long MOD;
vector<long long> fac,inv,finv;
long long C(long long x,long long y){if(x<0||y>x)return(0);return(fac[x]*finv[y]%MOD*finv[x-y]%MOD);}
long long power(long long b,long long n){b%=MOD;long long s=1;while(n){if(n%2==1)s=s*b%MOD;b=b*b%MOD;n/=2;}return s;}
void init(int n,long long mod){fac.resize(n+1);inv.resize(n+1);finv.resize(n+1);MOD=mod;fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1;for(long long i=1;i<=n;++i)fac[i]=fac[i-1]*i%MOD;for(long long i=2;i<=n;++i)inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;for(long long i=2;i<=n;++i)finv[i]=finv[i-1]*inv[i]%MOD;}
void init(long long mod){init(1000010,mod);}
long long Inv(int x){return power(x,MOD-2);}
};
#define int long long
const int MOD=998244353;
int n,a[1001],s;
void Delta() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(a[i]!=a[j])
s=(s+combi::C(n+i-j-1,n-j)*combi::power(2,j-i-1))%MOD;
cout << s << endl;
}
signed main() {
combi::init(10000,MOD);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
let $$$\text{cnt}_x=\sum\limits_{i=1}^n[a_i=x]$$$, and $$$b$$$ is a any integer.
if $$$\text{cnt}_x\le b$$$, we can do brute force in $$$\Theta(\text{cnt}_x^2)$$$. The worst-case complexity of this section is
if $$$\text{cnt}_x>b$$$, we can use NTT to solve it in $$$\Theta(n\log n)$$$.
let $$$d_k=[a_{n-k}=x]\frac{2^{n-k}}{k!}$$$,$$$e_k=(n-k-1)!$$$
This is a polynomial convolution form, so we can solve it using NTT in $$$\frac{n}{b}\times\Theta(n\log n)=\Theta(\frac{n^2}{b}\log n)$$$.
$$$\Theta(\frac{n^2}{b}\log n+nb)$$$ Is the smallest when $$$b=\Theta(\sqrt{n\log n})$$$, The total complexity is $$$\Theta(n\sqrt{n\log n})$$$
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
const int MOD=998244353,B=1001;
int fac[200001],inv[200001],finv[200001],invpw2[200001],a[200001];
vector<int> pw2(200001);
vector<int> Q[200001];
namespace NTT {
int a[262144],b[262144],r[262144],limit;
long long power(long long b,long long n) {
long long s=1;
while(n) {
if(n%2==1)
s=s*b%998244353;
b=b*b%998244353;
n/=2;
}
return s;
}
void NTT(int *a,int type) {
for(int i=0;i<limit;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int mid=1;mid<limit;mid<<=1) {
int wn=power(type==1?3:332748118,998244352/(mid<<1));
for(int j=0;j<limit;j+=mid<<1) {
long long w=1;
for(int k=0;k<mid;++k) {
int x=a[j+k],y=w*a[j+k+mid]%998244353;
a[j+k]=x+y>=998244353?x+y-998244353:x+y;
a[j+k+mid]=x<y?x-y+998244353:x-y;
w=w*wn%998244353;
}
}
}
}
void clear() {
for(int i=0;i<limit;++i)
a[i]=b[i]=r[i]=0;
}
void mul(int n,int m){
limit=1;int l=0;
while(limit<=n+m) {
limit<<=1;
++l;
}
for(int i=0;i<limit;++i)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
NTT(a,1);NTT(b,1);
for(int i=0;i<limit;++i)
a[i]=(long long)a[i]*b[i]%998244353;
NTT(a,-1);
long long inv=power(limit,998244351);
for(int i=0;i<=n+m;++i)
a[i]=inv*a[i]%998244353;
}
};
void Delta() {
int n,s=0; cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
Q[a[i]].push_back(i);
}
for(int x=1;x<=n;++x) {
if(Q[x].size()<=B) {
for(int i=0;i<(int)Q[x].size();++i)
for(int j=i+1;j<(int)Q[x].size();++j)
s=(s+(long long)pw2[Q[x][j]-Q[x][i]-1]*fac[n+Q[x][i]-Q[x][j]-1]%MOD*finv[n-Q[x][j]]%MOD*finv[Q[x][i]-1]%MOD)%MOD;
continue;
}
for(int i=0;i<=n-1;++i) {
NTT::a[i]=(long long)(a[n-i]==x)*pw2[n-i]*finv[i]%MOD;
NTT::b[i]=fac[n-i-1];
}
NTT::mul(n,n);
for(int i=1;i<=n;++i)
if(a[i]==x)
s=(s+(long long)(NTT::a[n-i]-(long long)pw2[i]*finv[n-i]%MOD*fac[n-1]%MOD+MOD)%MOD*finv[i-1]%MOD*invpw2[i+1]%MOD)%MOD;
NTT::clear();
}
cout << (n==1?0:((long long)(n-1)*pw2[n-2]%MOD-s+MOD)%MOD) << endl;
}
signed main() {
fac[0]=fac[1]=inv[0]=inv[1]=finv[0]=finv[1]=pw2[0]=invpw2[0]=1;
for(int i=1;i<=200000;++i) {
pw2[i]=(long long)pw2[i-1]*2%MOD;
invpw2[i]=(long long)invpw2[i-1]*499122177%MOD;
if(i==1) continue;
fac[i]=(long long)fac[i-1]*i%MOD;
inv[i]=MOD-(long long)MOD/i*inv[MOD%i]%MOD;
finv[i]=(long long)finv[i-1]*inv[i]%MOD;
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
For this problem, we can use brute force to enumerate numbers from small to large, then find the first one that is ok, output and end.
The reason for doing this is because we have an intuition: the smallest number that meets this condition will not be very large.
In fact, it's almost $$$\log a_i$$$ level, or even smaller.
#define int long long
void Delta() {
int n,x,i=2;
cin >> n >> x;
for(int i=1,t;i<n;++i) {
cin >> t;x=__gcd(x,t);
}
while(__gcd(x,i)-1) ++i;
cout << (x==1?0:i) << endl;
}
If a number appears more than half the $$$n$$$, it is impossible. Otherwise we can always greedily choose the two numbers that occur the most.
void Delta() {
int n,m;cin >> n >> m;
map<int,int> Q;
for(int i=1,x;i<=n;++i) {
cin >> x;
Q[x]++;
}
for(auto i:Q) if(i.second>n/2) {
cout << "NO\n";
return;
}
cout << "YES\n";
}
If a number has an odd number of factors, then the number must be the square of a positive integer.
Consider that when we do factorization, if a number $$$x$$$ is divisible by $$$n$$$, then n must correspond to two factors $$$x$$$ and $$$\frac{n}{x}$$$, unless $$$x=\frac{n}{x}$$$, in which case $$$n=x^2$$$.
This behavior looks like XOR in binary, so we put all the primes in a single bit and then do a map.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace Fact {
vector<char> isPrime;
vector<int> Prime,OneFac;
void GetPrime(int n){for(int i=0;i<n;++i)isPrime[i]=1;isPrime[1]=1;for(int i=2;i<=n;i++){if(isPrime[i])Prime.push_back(i);for(int j:Prime){if(i*j>n) break;isPrime[i*j]=0;OneFac[i*j]=j;if(i%j==0)break;}}}
void Fac_dfs(int x,int y,vector<int>& ans,vector<pair<int,int>>& FacList){if(x==(long long)(FacList.size())){ans.push_back(y);return;}int k=1;for(int i=0;i<=FacList[x].second;++i){Fac_dfs(x+1,y*k,ans,FacList);k*=FacList[x].first;}}
vector<pair<int,int>>GetPrimeFac(int a){vector<pair<int,int>>answer;if(isPrime[a])return(vector<pair<int,int>>{pair<int,int>{a,1}});answer.push_back({OneFac[a],1});a/=OneFac[a];while(!isPrime[a]){if(OneFac[a]==answer.back().first)answer.back().second++;else answer.push_back({OneFac[a],1});a/=OneFac[a];}if(a==answer.back().first)answer.back().second++;else answer.push_back({a,1});return(answer);}
vector<int>GetFacList(int a){vector<int> ans;vector<pair<int,int>>FacList=GetPrimeFac(a);Fac_dfs(0,1,ans,FacList);return(ans);}
void init(int n){isPrime.resize(n+2);OneFac.resize(n+2);GetPrime(n);}
void init(){init(10000005);}
};
#define int long long
int get(int x) {
int s=0;
for(int i=2,t=0;i<=300;++i)
if(Fact::isPrime[i]) {
while(x%i==0) {
s^=1ll<<t;
x/=i;
}
t++;
}
return s;
}
const int MOD=998244353;
int a[200001],pre[200001];
void Delta() {
int n,s=0;
map<int,int> Q={{0,1}}; cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=n;++i) {
pre[i]=pre[i-1]^get(a[i]);
s+=Q[pre[i]];Q[pre[i]]++;
}
cout << s << endl;
}
signed main() {
Fact::init(301);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
This is a dp problem.
Match from left to right. Since we can only link a maximum of $$$8$$$ lengths, anything before that won't affect the answer.
Make a bit mask dp, and maintain the state before $$$8$$$ lengths (already matched or not), you can finish.
If you need to use the values of the a array gcd in the innermost layer of dp, you can calculate and save them in advance, which can save a log of time.
$$$\Theta(nk2^k)$$$
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
int dp[100001][256],a[100001],n,k,s;
void Delta() {
cin >> n >> k;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=0;i<(1<<k)-1;++i) dp[0][i]=-2147483648;
for(int i=1;i<=n;++i) {
for(int j=0;j<1<<k;++j) dp[i][j]=-2147483648;
for(int j=0;j<1<<k;++j) {
dp[i][j*2%(1<<k)]=max(dp[i][j*2%(1<<k)],dp[i-1][j]);
dp[i][j*2%(1<<k)+1]=max(dp[i][j*2%(1<<k)+1],dp[i-1][j]);
}
for(int j=max(1ll,i-k);j<i;++j)
if(__gcd(a[i],a[j])==1)
for(int l=0;l<1<<k;++l)
if((l>>(i-j-1))%2==0) {
dp[i][(l+(1<<(i-j-1)))*2%(1<<k)+1]=max(dp[i][(l+(1<<(i-j-1)))*2%(1<<k)+1],dp[i-1][l]+1);
// if(dp[i-1][l]+1==2) {
// cerr << "? " << i << ' ' << j << ' ' << k << ' ' << l << endl;
// }
}
// for(int j=0;j<1<<k;++j) cerr << dp[i][j] << ' ';
// cerr << endl;
}
for(int i=0;i<1<<k;++i)
s=max(s,dp[n][i]);
cout << s << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
Firstly, do an inclusion-exclusion of the three intervals, and then the problem becomes the evaluation of the three intervals $$$[1,r1],[1,r2],[1,r3]$$$.
Then it's just for every prime number do classic digit dp.
I really don't know how to describe the solution to this kind of problem, sorry. =_=
// Code by problem setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << '\n';
}
template<int MOD>
struct Integral {
int v_ = 0;
Integral(int v) : v_(norm(v)) {}
Integral(long long v) : v_(norm(v)) {}
Integral(unsigned int v) : v_(norm(v)) {}
Integral(unsigned long long v) : v_(norm(v)) {}
Integral() = default;
~Integral() = default;
template<typename T> T norm(T v) const {
if constexpr(sizeof(T) > sizeof(MOD)) {
v %= MOD;
if (v < 0) v += MOD;
} else {
if (v >= MOD) v -= MOD;
if (v < 0) v += MOD;
if (v >= MOD || v < 0) {
v %= MOD;
if (v < 0) v += MOD;
}
}
return v;
}
int val() const { return v_; }
Integral& operator+=(const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
Integral& operator-=(const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
Integral& operator*=(const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
Integral& operator/=(const Integral& rhs) { v_ = v_ * 1LL * rhs.inv().val() % MOD; return *this; }
Integral operator+(const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
Integral operator-(const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
Integral operator*(const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
Integral operator/(const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
const Integral operator-() const { return Integral(-val()); }
const Integral& operator++() { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
const Integral operator++(int) { Integral ret = *this; ++(*this); return ret; }
const Integral& operator--() { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
const Integral operator--(int) { Integral ret = *this; --(*this); return ret; }
Integral power(long long b) const {
long long ret = 1 % MOD, a = v_;
for ( ; b; b >>= 1, a = a * a % MOD) { if (b & 1) ret = ret * a % MOD;} return ret;
}
Integral inv() const { return power(MOD - 2); }
std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
const int N = 31;
array<int, 6> getMask(int mask) {
array<int, 6> ret;
for (int i = 0; i < 6; ++i) {
ret[i] = (mask >> i & 1);
}
return ret;
}
int pr[N + 1];
void pre() {
pr[2] = 1;
for (int i = 3; i <= N; i += 2) {
int ok = 1;
for (int j = 2; j < i; ++j) {
ok &= (i % j != 0);
}
pr[i] = ok;
}
}
Mint solve(vector<int> x) {
Mint dp[N + 3][N + 3][2][2][2] {};
assert((int)x.size() == 3);
dp[N + 1][0][0][0][0] = 1;
for (int i = N; i >= 0; --i) {
int b1 = (x[0] >> i & 1);
int b2 = (x[1] >> i & 1);
int b3 = (x[2] >> i & 1);
for (int mask = 0; mask < (1 << 6); ++mask) {
auto [s1, s2, s3, c1, c2, c3] = getMask(mask);
if (!s1 && (c1 > b1)) continue;
if (!s2 && (c2 > b2)) continue;
if (!s3 && (c3 > b3)) continue;
for (int cnt = 0; cnt <= N; ++cnt) {
int ns1 = (s1 || c1 < b1);
int ns2 = (s2 || c2 < b2);
int ns3 = (s3 || c3 < b3);
int ad = c1 ^ c2 ^ c3;
dp[i][cnt + ad][ns1][ns2][ns3] += dp[i + 1][cnt][s1][s2][s3];
}
}
}
Mint ret = 0;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
for (int k = 0; k <= 1; ++k) {
for (int cnt = 2; cnt <= N; ++cnt) if (pr[cnt]) {
ret += dp[0][cnt][i][j][k];
}
}
}
}
return ret;
}
void solve() {
vector<int> l(3), r(3);
for (int i = 0; i < 3; ++i) {
cin >> l[i] >> r[i];
--l[i];
}
Mint ans = 0;
for (int mask = 0; mask < (1 << 3); ++mask) {
vector<int> x;
for (int i = 0; i < 3; ++i) {
if (mask >> i & 1) {
x.push_back(l[i]);
} else {
x.push_back(r[i]);
}
}
Mint cur = solve(x);
if (__builtin_popcount(mask) % 2 == 1) {
ans -= cur;
} else {
ans += cur;
}
}
cout << ans.val() << '\n';
}
int main() {
pre();
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}
Source : https://quera.org
First, it can be observed that for a given root, its value is $$$2^{\sum\limits_{\text{leaf}}2^{\text{dep[node]}}}-1$$$.
Since the power of two is going to grow very rapidly, exceeding all previous sums, it's intuitive that the node where we can get the answer should be near the mid point of the diameter. It can't exceed $$$\Theta(\log n)$$$ length.
So we start at the midpoint of the diameter. For each step, we greedily move to the subtree with the largest value of all the subtrees. It can calculate it in $$$\Theta(n\log n)$$$, So we can solve this problem in $$$\Theta(n\log^2 n)$$$.
Bonus: How to solve this problem in $$$\Theta(n)$$$?
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
class TreeLCA {
private:
vector<int> lca_top;
vector<bool> lca_hev;
bool lca_done;
void lca_dfs1(int p,int f,int d){int s=0,u=0;fa[p]=f;dep[p]=d;for(int i:tree[p]){if(i==f) continue;lca_dfs1(i,p,d+1);siz[p]+=siz[i];if(siz[i]>s){s=siz[i];u=i;}}siz[p]++;lca_hev[u]=true;}
void lca_dfs2(int p,int f){lca_top[p]=lca_hev[p]?lca_top[f]:p;for(int i:tree[p])if(i!=f)lca_dfs2(i,p);}
void diam_dfs(int x,int f,int dep,int& y,int &z){if(dep>y){y=dep;z=x;}for(int i:tree[x])if(i!=f)diam_dfs(i,x,dep+1,y,z);}
void gc_dfs(int x,int f,vector<int>& sz,vector<int>& we,vector<int> &ct){sz[x]=1;we[x]=0;for(int i:tree[x])if(i!=f){gc_dfs(i,x,sz,we,ct);sz[x]+=sz[i];we[x]=max(we[x],sz[i]);}we[x]=max(we[x],(int)sz.size()-1-sz[x]);if(we[x]<=((int)sz.size()-1)/2)ct.push_back(x);}
void dfn_dfs(int x,int f,int &cnt){dfn[x]=++cnt;for(int i:tree[x])if(i!=f)dfn_dfs(i,x,cnt);}
int jump(int v){return lca_hev[v]?lca_top[v]:fa[v];}
public:
typedef pair<int,int> path;
vector<vector<int>> tree;
vector<int> siz,dep,fa,dfn;
void resize(int n){tree.clear();tree.resize(n+1);}
void addedge(int u,int v){tree[u].push_back(v);tree[v].push_back(u);}
void init(int Root){int n=tree.size()-1,cnt=0;for(auto i:{&siz,&dep,&fa,&lca_top,&dfn}){i->clear();i->resize(n+1);}lca_hev.clear();lca_hev.resize(n+1);lca_dfs1(Root,0,1);lca_dfs2(Root,0);for(int i=1;i<=n;++i){if(fa[i]==0)continue;for(auto j=tree[i].begin();j<tree[i].end();++j)if(*j==fa[i]){swap(*j,tree[i].end()[-1]);break;}}dfn_dfs(Root,0,cnt);}
int lca(int u,int v){while(lca_top[u]!=lca_top[v]){if(dep[jump(u)]<dep[jump(v)])v=jump(v);else u=jump(u);}return(dep[u]<dep[v]?u:v);}
int dis(int u,int v){return dep[u]+dep[v]-dep[lca(u,v)]*2;}
int dis(path x){return dis(x.first,x.second);}
int nxt(int u,int v){if(u==v)return u;if(lca(u,v)!=u)return fa[u];return *(lower_bound(tree[u].begin(),tree[u].end()-(fa[u]!=0),v,[this](int x,int y)->int{return dfn[x]<=dfn[y];})-1);}
path inter(path a,path b){array<int,4>x{lca(a.first,b.first),lca(a.first,b.second),lca(a.second,b.first),lca(a.second,b.second)};sort(x.begin(),x.end(),[this](int x,int y)->int{return dep[x]>dep[y];});if(x[0]!=x[1]||dep[x[0]]==max(dep[lca(a.first,a.second)],dep[lca(b.first,b.second)]))return{x[0],x[1]};return{-1,-1};}
path diam(){int dep1=0,idx1=0,dep2=0,idx2=0;diam_dfs(1,0,0,dep1,idx1);diam_dfs(idx1,0,0,dep2,idx2);return{idx1,idx2};}
pair<int,int> gravity_center(){int n=tree.size()-1;vector<int>sz(n+1),we(n+1),ct;gc_dfs(1,0,sz,we,ct);ct.push_back(0);return{ct[0],ct[1]};}
TreeLCA(int n){resize(n);}TreeLCA(){}
};
TreeLCA Q;int n;
set<int> Get(int x,int fa) {
set<int> answer;
function<void(int)>add=[&](int x) {
if(answer.count(x)) {
answer.erase(x);
add(x+1);
} else answer.insert(x);
};
function<void(int,int,int)>dfs=[&](int x,int fa,int dep) {
if(Q.tree[x].size()==1) add(dep);
for(int i:Q.tree[x]) if(i!=fa) dfs(i,x,dep+1);
};
dfs(x,fa,-1);
return answer;
}
bool cmp(set<int> a,set<int> b) {
auto ia=a.rbegin(),ib=b.rbegin();
while(ia!=a.rend()&&ib!=b.rend()&&*ia==*ib){ia=next(ia);ib=next(ib);}
if(ia==a.rend()) return 0;
if(ib==b.rend()) return 1;
return *ia>*ib;
}
int nxt(int x) {
set<int> maxnum;int maxidx=0;
for(int i:Q.tree[x])
if(cmp(Get(i,x),maxnum)) {
maxnum=Get(i,x);
maxidx=i;
}
return maxidx;
}
int reach(int x) {
for(;;) {
int nxtt=nxt(x);
if(cmp(Get(nxtt,0),Get(x,0))||Get(nxtt,0)==Get(x,0)) break;
x=nxtt;
cout << ' ';
}
return x;
}
const int MOD=1000000007;
int calculate(int x) {
long long answer=1,powe=2;
set<int> Q=Get(x,0);
for(int i=0;i<=n;++i) {
if(Q.count(i)) answer=answer*powe%MOD;
powe=powe*powe%MOD;
}
return (answer-1+MOD)%MOD;
}
void Delta() {
cin >> n;Q.resize(n);
for(int i=1,u,v;i<n;++i) {
cin >> u >> v;
Q.addedge(u,v);
}
Q.init(1);
int node1=Q.diam().first,node2=Q.diam().second;
for(int t=Q.dis(node1,node2)/2,i=1;i<=t;++i)
node1=Q.nxt(node1,node2);
cout << calculate(reach(node1)) << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
#include"testlib.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> Gen1() { // # 25
vector<pair<int,int>> Q;
for(int i=1;i<=99;++i)
Q.push_back({i,i+1});
Q.push_back({50,101});
return Q;
}
vector<pair<int,int>> Gen2() { // # 26
vector<pair<int,int>> Q;
for(int i=1;i<=99;++i)
Q.push_back({i,i+1});
Q.push_back({51,101});
return Q;
}
vector<pair<int,int>> Gen3() { // # 27
vector<pair<int,int>> Q;
for(int i=1;i<=99;++i)
Q.push_back({i,i+1});
for(int i=101;i<=100000;++i)
Q.push_back({100,i});
return Q;
}
vector<pair<int,int>> Gen4() { // # 28
vector<pair<int,int>> Q;
for(int i=1;i<=49999;++i) Q.push_back({i,i+1});
for(int i=50000;i<=99999;++i) Q.push_back({i-49999,i+1});
return Q;
}
vector<pair<int,int>> Gen5() { // # 29
vector<pair<int,int>> Q;
for(int i=1;i<=49999;++i) Q.push_back({i,i+1});
for(int i=50000;i<=99899;++i) Q.push_back({i-49999,i+1});
for(int i=99901;i<=100000;++i) Q.push_back({i,1});
return Q;
}
vector<pair<int,int>> Gen6() { // # 31
vector<pair<int,int>> Q;
for(int i=1;i<=6;++i) Q.push_back({i,i+1});
Q.push_back({4,8});
for(int i=9;i<=100000;++i) Q.push_back({8,i});
return Q;
}
vector<pair<int,int>> Gen7() { // # 32
vector<pair<int,int>> Q;
for(int i=1;i<=49;++i) Q.push_back({i,i+1});
Q.push_back({2,51});
for(int i=52;i<=96;++i) Q.push_back({i,i-1});
for(int i=97;i<=150;++i) Q.push_back({i,96});
for(int i=151;i<=100000;i+=2) {
Q.push_back({i,1});
Q.push_back({i+1,i});
}
vector<int> P;
for(int i=1;i<=100000;++i) P.push_back(i);
shuffle(P.begin(),P.end());
for(int i=0;i<(int)Q.size();++i) {
Q[i].first=P[Q[i].first-1];
Q[i].second=P[Q[i].second-1];
}
return Q;
}
int main(int argc,char *argv[]) {
registerGen(argc,argv,1);
int n=opt<int>(1);
vector<pair<int,int>> Q;
if(n==1) Q=Gen1();
if(n==2) Q=Gen2();
if(n==3) Q=Gen3();
if(n==4) Q=Gen4();
if(n==5) Q=Gen5();
if(n==6) Q=Gen6();
if(n==7) Q=Gen7();
shuffle(Q.begin(),Q.end());
println(Q.size()+1);
for(auto i:Q)
println(i.first,i.second);
}
List will be updated after each round.
