Idea:Yugandhar_Master
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
cout<<((n+1)/2)*((m+1)/2)<<"\n";
}
}
Idea:beyondpluto
First let's assign a number to each sector from 1 to n in clockwise order.
One obvious construction is to move all cones to sector 1 as follows:
i) move cones at sector {2 and n} to sector 1, by moving both of them one unit towards sector 1 at each operation.
ii) move cones at sector {3,n-1} to sector 1 in same way.
iii) move cones at sector {4,n-2} to 1 in same way.
So on.
It takes ((n/2).(n/2+1))/2 ops. And it is minimum possible.
Consider parity of sum of sector numbers where cones are currently present. (with repeated count for multiple cones in same sector).
It is invariant in given operation. ie: it's parity doesn't change over any operation.
Our final state is something where all cones present in one same sector. And it's parity is always even as n is even. So, if parity of the initial state and final state are not same, then it's impossible to move to the final state from the initial state. And initial state parity is the parity of $$$1+2+3....+n = (n.(n+1))/2$$$ or just parity of $$$n/2$$$ as $$$n$$$ is already even.
So, it's impossible when the parity of $$$n/2$$$ is odd. Otherwise, it's always possible with the following construction for minimum possible operation:
Let's assume we want to move all cones to sector 1.
Always choose the top two cones that are farthest away from sector 1 and move them towards sector 1. On Each of this operation, the total sum of distance of all cones from sector 1 is decreased by two (which is maximum possible in one operation).
Initially total sum of distance is even(when $$$n/2$$$ is even) and it can be shown that our final operation will be with two different cones.
Notice that, after each of our operation, the distance between first farthest cone and second farthest cone doesn't go beyond one.
So, the minimum number of operations would be sum of initial (shortest)distance of all cones from sector 1, divided by two.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
if(n%2==0){
if((n/2)%2==1) cout<<"-1\n";
else{
ll x=(n/2);
cout<<(x*(x+1))/2-(n/4)<<"\n";
}
}
else{
ll x=(n-1)/2;
cout<<(x*(x+1))/2<<"\n";
}
}
}
Idea:Yugandhar_Master
#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
vector<int> v[1000010];
bool ch[1000010];
ll cnt1,cnt0;
void DFS(int po,bool c){
if(!c) cnt0++;
else cnt1++;
ch[po]=1;
for(auto i:v[po]){
if(!ch[i]){
DFS(i,!c);
}
}
return;
}
void solve(){
int n,a,b;
cnt1=0;
cnt0=0;
cin>>n;
for(int i=1;i<=n;i++){
v[i].clear();
ch[i]=0;
}
for(int i=1;i<n;i++){
cin>>a>>b;
v[a].eb(b);
v[b].eb(a);
}
DFS(1,0);
cout<<(((cnt1-1)*cnt1)/2)+(((cnt0-1)*cnt0)/2)<<'\n';
return;
}
int main(){
iofast
int t;
cin>>t;
w(t) solve();
return 0;
}
Idea:wuhudsm
Preparer:PROELECTRO444
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
if(k<n || k>(n*(n+1))/2) cout<<"-1\n";
else{
if(k==n){
for(ll i=1;i<n;i++) cout<<i<<" ";
cout<<0<<"\n";
}
else if(k==(n*(n+1))/2){
for(ll i=0;i<n;i++) cout<<i<<" ";
cout<<"\n";
}
else{
k-=n;
vector<ll> ans(n);
ll val=0,ind=0,ind1=0;
for(ll i=0;i<n;i++) ans[i]=i;
for(ll i=n-1;i>0;i--){
if(k>i) k-=i;
else{
swap(ans[i-1],ans[0]);
val=k;
ind=i;
break;
}
}
for(ll i=0;i<n;i++){
if(ans[i]==val){
ind1=i;
break;
}
}
swap(ans[ind],ans[ind1]);
for(auto i:ans) cout<<i<<" ";
cout<<"\n";
}
}
}
}
Idea:HexShift
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod=998244353;
const ll N=5e5+10;
vector<ll> po;
int main(){
fast;
po.resize(N);
po[0]=1;
for(ll i=1;i<N;i++) po[i]=(2*po[i-1])%mod;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0;i<n;i++) cin>>a[i];
vector<ll> dp(n);
vector<vector<ll>> v(n,vector<ll>(30));
vector<ll> val(30,0);
for(ll i=0;i<n;i++){
for(ll j=0;j<30;j++){
v[i][j]=val[j];
if((a[i]&(1<<j))>0) val[j]=1-val[j];
}
}
vector<vector<ll>> dp1(30,vector<ll>(2));
ll ans=0;
for(ll i=0;i<n;i++){
dp[i]=ans;
for(ll j=0;j<30;j++){
dp1[j][v[i][j]]=(dp1[j][v[i][j]]+((1<<j)*(po[max((ll)0,i-1)]))%mod)%mod;
}
for(ll j=0;j<30;j++){
if((a[i]&(1<<j))>0) dp[i]=(dp[i]+dp1[j][v[i][j]])%mod;
else dp[i]=(dp[i]+dp1[j][1-v[i][j]])%mod;
}
ans=(ans+dp[i])%mod;
}
cout<<dp[n-1]<<"\n";
}
}
Idea:Yugandhar_Master
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod=1e9+7;
long long power(long long a,long long b){
long long x=1,y=a;
while(b>0){
if(b&1ll){
x=(x*y)%mod;
}
y=(y*y)%mod;
b>>=1;
}
return x%mod;
}
long long modular_inverse(long long n){
return power(n,mod-2);
}
#define MAXN 2000005
long long factorial[MAXN];
long long invfact[MAXN];
void cfact(){
long long i;
factorial[0]=1;
factorial[1]=1;
for(i=2;i<MAXN;i++){
factorial[i]=factorial[i-1]*i;
factorial[i]%=mod;
}
invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
for(i=MAXN-2;i>=0;i--){
invfact[i]=invfact[i+1]*(i+1);
invfact[i]%=mod;
}
}
long long calcnCr(long long n,long long k){
if(k<0 || n<k){return 0;}
return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}
int main(){
fast;
cfact();
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
ll cnt11=count(s1.begin(),s1.end(),'1');
ll cnt20=count(s2.begin(),s2.end(),'0');
if(cnt11>0 && cnt20>0) cout<<"0\n";
else if(cnt11==0 && cnt20>0) cout<<power((power(2,n)-1)%mod,n-cnt20)%mod<<"\n";
else if(cnt11>0 && cnt20==0) cout<<power((power(2,n)-1)%mod,n-cnt11)%mod<<"\n";
else{
ll res=0;
for(ll i=0;i<n;i++){
if(i%2==0){
res=(res-((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod+mod)%mod;
}
else{
res=(res+((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod)%mod;
}
}
cout<<(power(2,n*n)+2*res)%mod<<"\n";
}
}
}
Idea:vikram108
WLOG, assume that $$$x \geq y$$$. We desire for Alice to win. Let us check the scenarios where this is possible:
Case 1: $$$(x \geq 2y)$$$: This means Alice has to subtract a multiple of $$$y$$$ from $$$x$$$. There are, say $$$k$$$ choices of subtracting $$$y, 2y, .., ky$$$. We have more than $$$1$$$ choices $$$(k>1)$$$. If $$$ky$$$ is winning, Alice chooses that. If it is losing, then since $$$k>1$$$, Alice can choose $$$(k-1)y$$$ and Bob will then be forces to subtract $$$y$$$ in the next move, essentially making Bob choose the losing $$$ky$$$ state. So Alice always wins.
Case 2: $$$(x<2y)$$$: This means there is only one possible move, which is to subtract $$$y$$$ from $$$x$$$. If the resulting pair of numbers $$$(y,x-y)$$$ is losing, Alice wins. Else she loses.
Now, for her to loose, like in case 1, $$$(y \geq 2(x-y))$$$ (we already know $$$y$$$ is larger than $$$(x-y)$$$ since $$$x<2y$$$). So for her to win, $$$y \leq 2(x-y)$$$, which means $$$x \geq \frac{3y}{2}$$$.
If $$$y<2(x-y)$$$, we again subtract and go to the next iteration. The new pair is $$$(x-y,2y-x)$$$. For it the winning conditions come out to be $$$x \geq \frac{5y}{3}$$$.
If we keep doing the iterations, we observe that in the $$$n^{th}$$$ step the condition comes out to be $$$x \geq \frac{F(n+1)}{F(n)}$$$ where $$$F(n)$$$ is the $$$n^{th}$$$ Fibonacci number $$$(F(1)=1, F(2)=2)$$$. So, to get the exact bound, we take its limit as $$$n$$$ approaches infinity, and get $$$\lim_{n \to \infty} \frac{F(n+1)}{F(n)} = \frac{1+\sqrt{5}}{2} = \phi$$$. So Alice wins iff $$$(x> \phi y)$$$ (equality dropped since both $$$x$$$ and $$$y$$$ are integers).
So our problem becomes counting the number of (l,r) such that r>phi*y. Since our numbers <=1e9, we can take an appropriate approximation of phi, (say p/q).
Now our problem boils down to calculatig sum of floor(xq/p) for x from some index l' till r. (here l' is the first index such that floor(l'q/p)>=l).
This is a standard problem and can be calculated in O(log(max(x,y)) complexity. Here is reference a blog with exact details about solving this: https://www.cnblogs.com/apjifengc/p/17492207.html
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll P = 998244353;
const ld phi=1.61803398874989;
const ll a=1134903170, b=0, c=1836311903;
struct Node {
ll x, y, sumx, sumy;
Node() : x(0), y(0), sumx(0), sumy(0) {}
Node operator*(Node b) {
Node a = *this, c;
c.x = (a.x + b.x) % P;
c.y = (a.y + b.y) % P;
c.sumx = (a.sumx + b.sumx + a.x * b.x) % P;
c.sumy = (a.sumy + b.sumy + a.y * b.x) % P;
return c;
}
};
Node pow(Node a, ll b) {
Node ans;
while (b) {
if (b & 1ll) ans = ans * a;
a = a * a;
b >>= 1ll;
}
return ans;
}
Node euclid(ll p, ll q, ll r, ll n, Node U, Node R) {
if (!n) return Node();
if (r >= q) return pow(U, r / q) * euclid(p, q, r % q, n, U, R);
if (p >= q) return euclid(p % q, q, r, n, U, pow(U, p / q) * R);
ll m = (1ll * p * n + r) / q;
if (!m) return pow(R, n);
return pow(R, (q - r - 1) / p) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U) * pow(R, n - (q * m - r - 1) / p);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Node U, R;
U.y = 1, R.x = 1, R.sumx = 1;
int t;cin>>t;while (t--){
ll l, r;cin>>l>>r;
ll sp=ceil(phi*l);
ll fa=(r-l+1)%P;
if (sp<=r){
ll ne=r-sp+1;
fa=(fa-((ne*(l-1))%P)+4*P)%P;
auto ans_r = euclid(a, c, b, r, U, R);
ans_r.sumy = (ans_r.sumy + (b / c)) % P;
auto ans_sp = euclid(a, c, b, sp-1, U, R);
ans_sp.sumy = (ans_sp.sumy + (b / c)) % P;
fa=(fa+ans_r.sumy-ans_sp.sumy+5*P)%P;
}
cout<<fa<<endl;
}
return 0;
}