結果

問題 No.911 ラッキーソート
ユーザー bin101
提出日時 2020-06-03 03:40:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 328 ms / 2,000 ms
コード長 14,458 bytes
コンパイル時間 1,346 ms
コンパイル使用メモリ 119,552 KB
実行使用メモリ 9,816 KB
最終ジャッジ日時 2024-11-25 02:17:27
合計ジャッジ時間 10,076 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
vectorvfill
vfill
*/
#pragma GCC optimize("Ofast")
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <iomanip>
#include <functional>
#include <complex>
using namespace std;
using ll=long long int;
using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;
// from
template<typename T >
struct Edge {
int from, to;
T cost;
Edge()=default;
Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
inline bool operator<(const Edge p)const noexcept{
return cost<p.cost;
}
inline bool operator>(const Edge p)const noexcept{
return cost>p.cost;
}
};
// from
template<typename T >
struct edge {
int to;
T cost;
edge()=default;
edge(int _to, T _cost) : to(_to), cost(_cost) {}
};
template<typename T>
using edges=vector<edge<T>>;
template<typename T>
using WeightGraph=vector<edges<T>>;
using Graph=vector<vector<int>>;
template<class T,class U>inline constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>inline constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
#define bit(n,k) ( ( (n)>>(k) )&1 )
inline void bin101(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout<<fixed<<setprecision(20);
}
//1-indexed vector cin
template<typename T>
inline void vin1(vector<T> &v){
for(size_t i=1;i<v.size();i++) cin>>v[i];
}
//0-indexed vector cin
template<typename T>
inline void vin0(vector<T> &v){
for(size_t i=0;i<v.size();i++) cin>>v[i];
}
//1-indexed vector<vector> cin
template<typename T>
inline void vin1(vector<vector<T>> &v){
for(size_t i=1;i<v.size();i++){
for(size_t j=1;j<v[i].size();j++) cin>>v[i][j];
}
}
//0-indexed vector<vector> cin
template<typename T>
inline void vin0(vector<vector<T>> &v){
for(size_t i=0;i<v.size();i++){
for(size_t j=0;j<v[i].size();j++) cin>>v[i][j];
}
}
bool DEBUG_MODE=false;
#define debug(a) if(DEBUG_MODE){cout<<#a;PRINT(a);cout<<flush;}
#define debug2(a,b) if(DEBUG_MODE){debug(a);debug(b);}
#define debug3(a,b,c) if(DEBUG_MODE){debug(a);debug(b);debug(c);}
#define debug4(a,b,c,d) if(DEBUG_MODE){debug(a);debug(b);debug(c);debug(d);}
#define debug5(a,b,c,d,e) if(DEBUG_MODE){debug(a);debug(b);debug(c);debug(d);debug(e);}
#define gdebug(x) if(DEBUG_MODE){cout<<#x;GPRINT(x);}
template<class T>void PRINT(const T x){cout<<":"<<x<<"\n";}
//
template<typename T>
void PRINT(const vector<T> &v,int a=-1){
if(!DEBUG_MODE) return;
cout<<":1d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
cout<<i<<":"<<v[i]<<'\n';
}
cout<<"\n";
}
//
template<typename T>
void PRINT(const vector<vector<T>> &v,int a=-1,int b=-1){
if(!DEBUG_MODE) return;
cout<<":2d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
for(size_t j=0;j<v[i].size() and (b<0 or j<=(size_t)b);j++){
cout<<i<<"-"<<j<<":"<<v[i][j]<<"\n";
}
}
cout<<"\n";
}
//
template<typename T>
void PRINT(const vector<vector<vector<T>>> &v,int a=-1,int b=-1,int c=-1){
if(!DEBUG_MODE) return;
cout<<":3d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
for(size_t j=0;j<v[i].size() and (b<0 or j<=(size_t)b);j++){
for(size_t k=0;k<v[i][j].size() and (c<0 or k<=(size_t)c);k++){
cout<<i<<"-"<<j<<"-"<<k<<":"<<v[i][j][k]<<"\n";
}
}
}
cout<<"\n";
}
//
template<typename T>
void PRINT(const vector<vector<vector<vector<T>>>> &v,int a=-1,int b=-1,int c=-1,int d=-1){
if(!DEBUG_MODE) return;
cout<<":4d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
for(size_t j=0;j<v[i].size() and (b<0 or j<=(size_t)b);j++){
for(size_t k=0;k<v[i][j].size() and (c<0 or k<=(size_t)c);k++){
for(size_t l=0;l<v[i][j][k].size() and (d<0 or l<=(size_t)d);l++){
cout<<i<<"-"<<j<<"-"<<k<<"-"<<l<<":"<<v[i][j][k][l]<<"\n";
}
}
}
}
cout<<"\n";
}
//
template<typename T>
void PRINT(const vector<vector<vector<vector<vector<T>>>>> &v,int a=-1,int b=-1,int c=-1,int d=-1,int e=-1){
if(!DEBUG_MODE) return;
cout<<":5d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
for(size_t j=0;j<v[i].size() and (b<0 or j<=(size_t)b);j++){
for(size_t k=0;k<v[i][j].size() and (c<0 or k<=(size_t)c);k++){
for(size_t l=0;l<v[i][j][k].size() and (d<0 or l<=(size_t)d);l++){
for(size_t m=0;m<v[i][j][k][l].size() and (e<0 or m<=(size_t)e);m++){
cout<<i<<"-"<<j<<"-"<<k<<"-"<<l<<"-"<<m<<":"<<v[i][j][k][l][m]<<"\n";
}
}
}
}
}
cout<<"\n";
}
template<typename T>
void PRINT(const set<T> &S){
if(!DEBUG_MODE) return;
int now=0;
for(auto x:S){
cout<<now++<<":"<<x<<"\n";
}
}
template<typename T,typename U>
void PRINT(const map<T,U> &M){
if(!DEBUG_MODE) return;
cout<<":map\n";
size_t now=0;
for(auto &x:M){
cout<<now++<<":"<<x<<"\n";
}
}
//()
template<typename T>
void GPRINT(const vector<T> &v,int a=-1){
if(!DEBUG_MODE) return;
cout<<":1d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
if(i) cout<<",";
cout<<v[i];
}
}
//()
template<typename T>
void GPRINT(const vector<vector<T>> &v,int a=-1,int b=-1){
if(!DEBUG_MODE) return;
cout<<":2d\n";
for(size_t i=0;i<v.size() and (a<0 or i<=(size_t)a);i++){
for(size_t j=0;j<v[i].size() and (b<0 or j<=(size_t)b);j++){
if(j) cout<<",";
cout<<v[i][j];
}
cout<<"\n";
}
}
//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
os<<p.first<<" "<<p.second;
return os;
}
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
is>>p.first>>p.second;
return is;
}
//
template<typename T>
inline void vsort(vector<T> &v){
sort(v.begin(),v.end());
}
//
template<typename T>
inline void rvsort(vector<T> &v){
sort(v.rbegin(),v.rend());
}
//n x
template<typename T>
inline vector<T> vmake(size_t n,T x){
return vector<T>(n,x);
}
//a,b,c,x data[a][b][c] x
template<typename... Args>
auto vmake(size_t n,Args... args){
auto v=vmake(args...);
return vector<decltype(v)>(n,move(v));
}
template<typename T,typename... X>
inline void vfill(T &t,const X... x){
t=T(x...);
}
template<typename T,typename... X>
void vfill(vector<T> &t,const X... x){
for(auto &s:t) vfill(s,x...);
}
//
template<typename T>
void vout(const vector<T> &v,string s=" ",size_t f=0,int t=-1){
for(size_t i=f;i<v.size() and(t<0 or i<=(size_t)t);i++){
if(i!=f) cout<<s;
cout<<v[i];
}
cout<<"\n";
}
//
template<typename T>
void vout(const vector<vector<T>> &v,string s=" ",int fh=0,int th=-1,int fw=0,int tw=-1){
for(size_t i=fh;i<v.size() and (th<0 or i<=(size_t)th);i++){
for(size_t j=fw;j<v[i].size() and (tw<0 or j<=(size_t)tw);j++){
if(j!=fw) cout<<s;
cout<<v[i][j];
}
cout<<"\n";
}
}
//1
inline int popcount(int x){
return __builtin_popcount(x);
}
//1
inline int popcount(ll x){
return __builtin_popcountll(x);
}
constexpr int MAX=(1<<30)-1;
constexpr ll INF=(1LL<<62)-1;
constexpr ll MOD=1000000007;
constexpr int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
struct ModInt{
using u64=uint_fast64_t;
u64 a;
constexpr ModInt() :a(0){}
constexpr ModInt(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {}
inline constexpr ModInt operator+(const ModInt rhs)const noexcept{
return ModInt(*this)+=rhs;
}
inline constexpr ModInt operator-(const ModInt rhs)const noexcept{
return ModInt(*this)-=rhs;
}
inline constexpr ModInt operator*(const ModInt rhs)const noexcept{
return ModInt(*this)*=rhs;
}
inline constexpr ModInt operator/(const ModInt rhs)const noexcept{
return ModInt(*this)/=rhs;
}
inline constexpr ModInt operator+(const ll rhs) const noexcept{
return ModInt(*this)+=ModInt(rhs);
}
inline constexpr ModInt operator-(const ll rhs)const noexcept{
return ModInt(*this)-=ModInt(rhs);
}
inline constexpr ModInt operator*(const ll rhs)const noexcept{
return ModInt(*this)*=ModInt(rhs);
}
inline constexpr ModInt operator/(const ll rhs)const noexcept{
return ModInt(*this)/=ModInt(rhs);
}
inline constexpr ModInt &operator+=(const ModInt rhs)noexcept{
a+=rhs.a;
if(a>=MOD) a-=MOD;
return *this;
}
inline constexpr ModInt &operator-=(const ModInt rhs)noexcept{
if(rhs.a>a) a+=MOD;
a-=rhs.a;
return *this;
}
inline constexpr ModInt &operator*=(const ModInt rhs)noexcept{
a=(a*rhs.a)%MOD;
return *this;
}
inline constexpr ModInt &operator/=(ModInt rhs)noexcept{
a=(a*rhs.inverse().a)%MOD;
return *this;
}
inline constexpr ModInt &operator+=(const ll rhs)noexcept{
return *this+=ModInt(rhs);
}
inline constexpr ModInt &operator-=(const ll rhs)noexcept{
return *this-=ModInt(rhs);
}
inline constexpr ModInt &operator*=(const ll rhs)noexcept{
return *this*=ModInt(rhs);
}
inline constexpr ModInt &operator/=(const ll rhs)noexcept{
return *this/=ModInt(rhs);
}
inline constexpr ModInt operator=(const ll x)noexcept{
a=(x>=0)?(x%MOD):(x%MOD+MOD);
return *this;
}
inline constexpr bool operator==(const ModInt p)const noexcept{
return a==p.a;
}
inline constexpr bool operator!=(const ModInt p)const noexcept{
return a!=p.a;
}
inline constexpr ModInt pow(ll N) const noexcept{
ModInt ans(1LL),p(a);
while(N>0){
if(bit(N,0)){
ans*=p;
}
p*=p;
N>>=1;
}
return ans;
}
inline constexpr ModInt inverse() const noexcept{
return pow(MOD-2);
}
};
inline constexpr ModInt operator+(const ll &a,const ModInt &b)noexcept{
return ModInt(a)+=b;
}
inline constexpr ModInt operator-(const ll &a,const ModInt &b)noexcept{
return ModInt(a)-=b;
}
inline constexpr ModInt operator*(const ll &a,const ModInt &b)noexcept{
return ModInt(a)*=b;
}
inline constexpr ModInt operator/(const ll &a,const ModInt &b)noexcept{
return ModInt(a)/=b;
}
//cout
inline ostream &operator<<(ostream &os,const ModInt &p) {
return os<<p.a;
}
//cin
inline istream &operator>>(istream &is,ModInt &p) {
ll t;
is>>t;
p=t;
return is;
}
struct Binominal{
vector<ModInt> fac,finv,inv; //fac[n]:n! finv:(n!)
int sz;
Binominal(int n=10) :sz(1){
if(n<=0) n=10;
init(n);
}
inline void init(int n){
fac.resize(n+1,1);
finv.resize(n+1,1);
inv.resize(n+1,1);
for(int i=sz+1;i<=n;i++){
fac[i]=fac[i-1]*i;
inv[i]=MOD-inv[MOD%i]*(MOD/i);
finv[i]=finv[i-1]*inv[i];
}
sz=n;
}
//nCk(n,k<=N) O(1)
inline ModInt com(int n,int k){
if(n<k) return ModInt(0);
if(n<0 || k<0) return ModInt(0);
if(n>sz) init(n);
return fac[n]*finv[k]*finv[n-k];
}
//nCk(k<=N) O(k) 
inline ModInt rcom(ll n,int k){
if(n<0 || k<0 || n<k) return ModInt(0);
if(k>sz) init(k);
ModInt ret(1);
for(int i=0;i<k;i++){
ret*=n-i;
}
ret*=finv[k];
return ret;
}
// nk
//n,|k
inline ModInt h(int n,int k){
return com(n+k-1,k);
}
};
ll GCD(ll a,ll b){
if(a==0 or b==0) return 0;
while(a%b!=0){
ll t=a%b;
a=b;
b=t;
}
return b;
}
ll f(vector<ll> A,ll R){
int N=A.size();
if(R<0) return 0;
//dp[i][j] j0 1 ibit
auto dp=vmake(62,2,0LL);
dp[61][0]=1;
vector<bool> up(N);
for(int I=61;I>=1;I--){
debug2(I,up);
vector<int> v;
for(int i=1;i<N;i++){
if(bit(A[i-1],I-1)==bit(A[i],I-1) or up[i]){
v.push_back(2);
}else{
v.push_back(bit(A[i-1],I-1));
up[i]=true;
}
}
debug(v);
int num=-1;
for(int i=0;i<N-1;i++){
if(v[i]==2) continue;
if(num==-1){num=v[i];}
if(num!=v[i]) return 0;
}
for(int j=0;j<2;j++){
//
if(num==1 or num==-1){
if(j==0 and bit(R,I-1)==0) ;
else dp[I-1][j]+=dp[I][j];
}
if(num==0 or num==-1){
if(bit(R,I-1)==0) dp[I-1][j]+=dp[I][j];
else dp[I-1][1]+=dp[I][j];
}
}
}
debug(dp);
return dp[0][0]+dp[0][1];
}
int main(){
DEBUG_MODE=false;
bin101();
//++++++++++++++++++++++++++++++++++++++//
int N;
cin>>N;
ll L,R;
cin>>L>>R;
vector<ll> A(N);
vin0(A);
ll ret=f(A,R)-f(A,L-1);
cout<<ret<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0