@KirinBill
2017-11-01T07:27:35.000000Z
字数 4795
阅读 1076
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <cmath>
using std::sqrt;
const int MAXN=1e7+5;
int phi[MAXN];
inline void Euler_phi(int n){
static int prm[MAXN];
static bool notP[MAXN];
notP[1]=true,phi[1]=1;
for(int i=2;i<=n;++i){
if(!notP[i]){
prm[++prm[0]]=i;
phi[i]=i-1;
}
for(int j=1,tmp;j<=prm[0] && i*prm[j]<=n;++j){
tmp=i*prm[j];
notP[tmp]=true;
if(i%prm[j]==0){
phi[tmp]=phi[i]*prm[j];
break;
}
else phi[tmp]=phi[i]*phi[prm[j]];
}
}
}
inline unsigned long long cal(long long n){
int sqrt_n=sqrt(n);
Euler_phi(sqrt_n);
unsigned long long ret=0;
for(int i=2;i<=sqrt_n;++i)
ret+=(unsigned long long)phi[i]*(n/i/i);
return ret;
}
int main(){
#ifdef DEBUG
setIO("a");
#endif
long long n;
read(n);
write(cal(n));
return 0;
}
upper_bound
做法似乎就行不通了;
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=100005,P=123456789;
int n,maxr;
int r[MAXN];
struct query{
int sz;
long long sum;
query(int sz=0,long long sum=0):sz(sz),sum(sum){}
};
class val_segT{
#define ls (u<<1)
#define rs (ls|1)
private:
typedef query node;
node d[MAXN<<2];
void upd(int u){
if(d[ls].sz>d[rs].sz) d[u]=d[ls];
else if(d[rs].sz>d[ls].sz) d[u]=d[rs];
else d[u]=node(d[ls].sz,(d[ls].sum+d[rs].sum)%P);
}
void ist(int u,int l,int r,int pos,query &val){
if(l==r){
if(d[u].sz<val.sz) d[u]=val;
else if(d[u].sz==val.sz)
d[u].sum=(d[u].sum+val.sum)%P;
return;
}
int mid=l+r>>1;
if(pos<=mid) ist(ls,l,mid,pos,val);
else ist(rs,mid+1,r,pos,val);
upd(u);
}
query qry(int u,int l,int r,int lp,int rp){
if(lp<=l && r<=rp) return d[u];
int mid=l+r>>1;
query ret,tmp;
if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
if(rp>mid){
tmp=qry(rs,mid+1,r,lp,rp);
if(tmp.sz>ret.sz) ret=tmp;
else if(tmp.sz==ret.sz) ret.sum=(ret.sum+tmp.sum)%P;
}
return ret;
}
public:
void ist(int pos,query &val){ist(1,1,maxr,pos,val);}
query qry(int rp){
if(rp<=0) return query(0,0);
return qry(1,1,maxr,1,rp);
}
#undef ls
#undef rs
}T;
inline query DP(){
query ret,tmp;
for(int i=1;i<=n;++i){
tmp=T.qry(r[i]-1);
if(tmp.sz==0) tmp.sum=1;
++tmp.sz;
if(ret.sz<tmp.sz) ret=tmp;
else if(ret.sz==tmp.sz) ret.sum=(ret.sum+tmp.sum)%P;
T.ist(r[i],tmp);
}
return ret;
}
int main(){
#ifdef DEBUG
setIO("b");
#endif
int type;
read(n),read(type);
for(int i=1;i<=n;++i){
read(r[i]);
maxr=max(maxr,r[i]);
}
query ans=DP();
write(ans.sz,'\n');
if(type) write(ans.sum);
return 0;
}
#include <cstdio>
#include <algorithm>
using std::max;
const int MAXN=5005,P=123456789;
int n;
long long ans[MAXN<<1];
long long wht[MAXN],blk[MAXN];
long long sumw[MAXN],sumb[MAXN];
inline void pre_cal(){
wht[1]=1,wht[2]=0,wht[3]=1;
for(int i=4;i<=n;++i)
wht[i]=(wht[i-1]+wht[i-2])%P;
blk[1]=0,blk[2]=1;
for(int i=3;i<=n;++i)
blk[i]=(blk[i-1]+blk[i-2])%P;
for(int i=1;i<=n;++i){
sumw[i]=(sumw[i-1]+wht[i])%P;
sumb[i]=(sumb[i-1]+blk[i])%P;
}
}
inline void solve(){
for(int i=1;i<=n;++i)
ans[i]=sumw[n-i]*wht[i+1]%P;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
ans[i+j]=(ans[i+j]+sumb[n-max(i,j)]*wht[i]%P*blk[j]%P)%P;
}
}
int main(){
scanf("%d",&n);
pre_cal();
solve();
for(int i=1,lim=n<<1;i<=lim;++i)
printf("%d ",ans[i]);
return 0;
}