Idea:Yugandhar_Master
/
solution
code(C++)
#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
/
solution
code(C++)
#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
/
solution
code(C++)
#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
solution
code(C++)
#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 /
solution
code(C++)
#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 \
solution
code(C++)
#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
\
solution
code(C++)
#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;
}