小楼昨夜又西北风
#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int N=1e5+7,M=1e6+7;
struct Question{
int l,r,id;
}q[N];
int n,m,cnt=1,tot;
int a[N],c[N],num[N],pos[N],ans[N],f[M],prime[N],inv[N];
bool check[M];
int qread()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
bool cmp(const Question &a,const Question &b)
{
if(pos[a.l]==pos[b.l])return a.r<b.r;
return pos[a.l]<pos[b.l];
}
void Change(int x,int v)
{
cnt=1ll*cnt*inv[f[num[a[x]]]]%mod;
num[a[x]]+=v*c[x];
cnt=1ll*cnt*f[num[a[x]]]%mod;
}
void Init()
{
check[1]=1;
for(int i=2;i<M;i++)
{
if(!check[i])prime[++tot]=i,f[i]=1;
for(int j=1;j<=tot && i*prime[j]<M;j++)
{
check[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
f[0]=1;
for(int i=1;i<M;i++)f[i]+=f[i-1];
inv[1]=1;
for(int i=2;i<N;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
int sqr=sqrt(n);
for(int i=1;i<=n;i++)pos[i]=(i-1)/sqr+1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
a[i]=qread();
for(int i=1;i<=n;i++)
c[i]=qread();
for(int i=1;i<=m;i++)
{
q[i].l=qread();q[i].r=qread();
q[i].id=i;
}
Init();
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
while(r<q[i].r)Change(++r,1);
while(r>q[i].r)Change(r--,-1);
while(l<q[i].l)Change(l++,-1);
while(l>q[i].l)Change(--l,1);
ans[q[i].id]=cnt;
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
下雨了,可以来拯救吗?
#include<complex>
#include<cstdio>
using namespace std;
const int mod=998244353;
long long n;
int Fpow(long long b,int p)
{
long long res=1;
for(;p;p>>=1,b=b*b%mod)
if(p&1)res=res*b%mod;
return res;
}
int main()
{
scanf("%lld",&n);
long long ans=0;
for(long long l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(r-l+1)*(n/l)%mod;
}
printf("%d\n",ans%mod*Fpow(n%mod,mod-2)%mod);
return 0;
}
玫瑰依在
#include<complex>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+7;
int n,m,cnt;
long long K;
int a[N],b[N],c[N],d[N],e[N];
int qread()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int Lowbit(int x){return x&-x;}
void Add(int x)
{
for(;x<=m;x+=Lowbit(x))
c[x]++;
}
int Query(int x)
{
int res=0;
for(;x;x-=Lowbit(x))
res+=c[x];
return res;
}
int Find(int x)
{
int l=1,r=m,mid;
while(l<r)
if(d[mid=l+r>>1]<x)l=mid+1;
else r=mid;
return l;
}
void Discrete()
{
sort(d+1,d+n+2);
d[0]=-1;m=0;
for(int i=1;i<=n+1;i++)
if(d[i]!=d[i-1])d[++m]=d[i];
for(int i=0;i<=n;i++)
e[i]=Find(e[i]);
}
long long check(int x)
{
for(int i=1;i<=n;i++)
e[i]=e[i-1]+(a[i]>=x);
for(int i=0;i<=n;i++)
e[i]=e[i]*2-i,d[i+1]=e[i];
Discrete();
memset(c,0,sizeof(c));
long long res=0;
for(int i=0;i<=n;i++)
if(i&1)Add(e[i]);
else res+=Query(e[i]-1);
memset(c,0,sizeof(c));
for(int i=0;i<=n;i++)
if(i&1)res+=Query(e[i]-1);
else Add(e[i]);
return res;
}
int main()
{
scanf("%d%lld",&n,&K);
for(int i=1;i<=n;i++)
b[i]=a[i]=qread();
b[0]=-1;
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
if(b[i]!=b[i-1])b[++cnt]=b[i];
int l=1,r=cnt,res=0;
while(l<=r)
{
int mid=l+r>>1;
long long t=check(b[mid]);
if(t>=K)l=mid+1,res=mid;
else r=mid-1;
}
printf("%d\n",b[res]);
return 0;
}
拼不出的数
#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n;
int a[N];
int qread()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i]=qread();
sort(a+1,a+n+1);
long long sum=0;
for(int i=1;i<=n;i++)
if(a[i]>sum+1)
{
printf("%lld\n",sum+1);
return 0;
}
else sum+=a[i];
printf("%lld\n",sum+1);
return 0;
}
樱花般的爱情
#include<complex>
#include<cstdio>
using namespace std;
const int mod=1e9+7;
const int N=5e5+7;
int n;
long long ans;
int s[N>>1],a[N<<1];
int Fpow(long long b,int p)
{
long long res=1;
for(;p;p>>=1,b=b*b%mod)
if(p&1)res=res*b%mod;
return res;
}
int main()
{
scanf("%d",&n);
s[0]=1;
for(int i=1;i*2<=n;i++)
s[i]=1ll*s[i-1]*(2*i-1)%mod;
for(int i=n+1;i<=n+n-1;i++)
{
a[i]=1ll*Fpow(i-n,n-i/2)*s[i-n>>1]%mod;
ans+=1ll*i*(a[i]-a[i-1])%mod;
}
printf("%d\n",(ans%mod+mod)*Fpow(s[n>>1],mod-2)%mod);
return 0;
}
她的字符串
#include<complex>
#include<cstdio>
using namespace std;
const int N=27,M=1e6+7;
int n,ans;
int last[N],num[N],p[N][N],minv[N][N];
char s[M];
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
{
int c=s[i]-'a';
num[c]++;last[c]=i;
for(int j=0;j<26;j++)
if(j!=c && num[j])
ans=max(ans,max(num[c]-num[j]-minv[c][j]-(last[j]==p[c][j]),num[j]-num[c]-minv[j][c]-(last[j]==p[j][c])));
for(int j=0;j<26;j++)
{
if(num[c]-num[j]<minv[c][j])
{
minv[c][j]=num[c]-num[j];
p[c][j]=i;
}
if(num[j]-num[c]<minv[j][c])
{
minv[j][c]=num[j]-num[c];
p[j][c]=i;
}
}
}
printf("%d\n",ans);
return 0;
}
虚幻的十字架
#include<complex>
#include<cstdio>
using namespace std;
const int N=101;
int n,tot;
char s[N][N];
bool vis[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(s[i][j]=='#' && !vis[i][j])
if(s[i+1][j-1]=='#' && s[i+1][j]=='#' && s[i+1][j+1]=='#' && s[i+2][j]=='#')
vis[i+1][j-1]=vis[i+1][j]=vis[i+1][j+1]=vis[i+2][j]=1;
else
{
printf("NO\n");
return 0;
}
printf("YES\n");
return 0;
}
顽皮的她与消失的数字
#include<complex>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,m;
int a[N],b[N];
int qread()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i]=qread();
scanf("%d",&m);
for(int i=1;i<=m;i++)
b[i]=qread();
sort(a+1,a+n+1);sort(b+1,b+m+1);
int i=1,j=1;
while(i<=n)
if(a[i]!=b[j])printf("%d ",a[i++]);
else i++,j++;
return 0;
}