城乡联谊胡策会糊厕R3

时间:2021-06-14 23:20:45

因为时间关系这把没设计题面,而且居然还出了锅……T_T

  原题是leetcode WeeklyContest52 的T1(懒得去找url了

  随便搞,但是无解输-1

数字统计

原题PE603

  记前n个素数组成的字符串为S

  一个数字可以分成三部分,中间一段恰好为S复制某次后的结果,前面一段S的后缀,后面一段S的前缀。这3个部分分开统计。

  对于每个部分,我们可以很容易写出一份暴力,然后用自然数k次前缀和的公式优化一波就可以了。

#include<ctime>
#include<cassert>
#include<cstdio>
#include<algorithm>
#define MN 2000001
#define int long long
#define ju(x) assert(1||(x)>=0&&x<MOD)
using namespace std; const int MOD=1e9+;
int p[MN],sum=,num=,K,mmh,s[MN],n,pre[MN],suf[MN];
bool bo[MN];
inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}
inline int mi(long long x,long long y){
int mmh=;
while (y){
if (y&) mmh=1LL*mmh*x%MOD;
x=1LL*x*x%MOD;y>>=;
}
return mmh;
}
signed main(){
for (int i=;i<MN;i++){
if (!bo[i]) p[++num]=i;
for (int j=;j<=num&&i*p[j]<MN;j++)
if (bo[i*p[j]]=,i%p[j]==) break;
}
num=;K=1000000000000ll;
//freopen("data/count1.in","r",stdin);
//freopen("data/count1.out","w",stdout);
//num=10000;K=1000000000000ll;
//num=23;K=233;
scanf("%lld%lld",&num,&K);
mmh=n=;
for (int i=num;i;i--)
for (int j=p[i];j;j/=) s[n++]=j%;
for (int i=;i<n/;i++) swap(s[i],s[n--i]);
for (int i=;i<n;i++) M(pre[i]=pre[i-]*%MOD+s[i]);
for (int i=n-,k=;i>=;i--,k=1LL*k*%MOD) M(suf[i]=1LL*s[i]%MOD*k%MOD+suf[i+]); for (int i=,j=;i<n;i++)
j=(1LL*j%MOD*%MOD+1LL*s[i]%MOD*(i+)%MOD)%MOD,M(mmh+=j);
mmh=1LL*K%MOD*mmh%MOD;
for (int i=;i<n;i++) sum=(1LL*sum*+s[i])%MOD;
int MMH=1LL*K%MOD*((K-)%MOD)%MOD*mi(,MOD-)%MOD*%MOD,_MMH=,a=mi(,MOD-);
MMH=MOD-MMH;
ju(MMH);ju(_MMH); //for (int i=0;i<K;i++) _MMH=(1LL*i%MOD*mi(a,i*n)+_MMH)%MOD;
int b=mi(a,n);
M(_MMH=((1LL*(K-)%MOD*mi(b,K)+)%MOD*mi(b-,MOD-)%MOD-(1LL*mi(b,K)-)%MOD*mi(b-,MOD-)%MOD*mi(b-,MOD-)%MOD)%MOD);
ju(MMH);ju(_MMH); _MMH=1LL*_MMH%MOD*mi(,K*n-n+)%MOD;
M(mmh+=1LL*(MMH+_MMH)%MOD*n%MOD*sum%MOD*mi(,MOD-)%MOD);
ju(MMH);ju(_MMH);
for (int i=;i<n;i++){
int MMH=1LL*(mi(,K*n)-)%MOD*mi(mi(,n)-,MOD-)%MOD;
ju(MMH); MMH=MMH*%MOD;
M(MMH-=K*%MOD);
ju(MMH);
M(mmh+=suf[i]%MOD*mi(,MOD-)%MOD*MMH%MOD);
ju(mmh);
} for (int i=;i<n;i++){
int MMH=1LL*K%MOD*((K-)%MOD)%MOD*mi(,MOD-)%MOD;
ju(MMH);
M(mmh+=1LL*pre[i]%MOD*n%MOD*MMH%MOD);
ju(mmh);
}
printf("%lld\n",mmh);
return ; mmh=n=;
for (int k=;k<=K;k++)
for (int i=num;i;i--)
for (int j=p[i];j;j/=) s[n++]=j%;
for (int i=;i<n/;i++) swap(s[i],s[n--i]);
for (int i=,j=;i<n;i++)
j=(1LL*j%MOD*%MOD+1LL*s[i]%MOD*(i+))%MOD,M(mmh+=j);
printf("%lld\n",mmh);
return ; mmh=n=;
for (int k=;k<=K;k++)
for (int i=num;i;i--)
for (int j=p[i];j;j/=) s[n++]=j%;
for (int i=n-;i>=;i--)
for (int j=i,k=;j>=;j--)
k=(1LL*k*+s[j])%MOD,M(mmh+=k);
printf("%d\n",mmh);
}

飞翔

原题 Codility Chromium 2017

  首先把数字从大到小排个序,然后从1到n枚举以每棵树为起点的序列数,这样就每次只有一棵树从在右边的状态变成在左边的状态。

  问题变成,一列格子,一些是黑色的,一些是白色的,你需要从左往右走,每次可以走到当前格子右边的任意一个点,相邻两次踩到的格子必须颜色不同。这个问题显然可以直接递推。考虑到要进行修改操作,我们可以用线段树维护矩阵乘法实现。

  出题人写了3次觉得这玩意贼好写啊(不到2k的线段树

#include<cstdio>
#include<algorithm>
#define lp p<<1
#define rp (p<<1)|1
#define MN 400000
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
int n,m,a[MN],b[MN],t[MN*][][],C[][],Mavis[][],mmh=;
const int MOD=1e9+;
inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}
bool cmp(int x,int y){return a[x]>a[y];}
void cc(int a[][],int b[][],int c[][]){
int i,j,k;
for (i=;i<;i++)
for (j=;j<;j++)
for (C[i][j]=,k=;k<;k++) C[i][j]=(1LL*a[i][k]*b[k][j]+C[i][j])%MOD; for (i=;i<;i++)
for (j=;j<;j++) c[i][j]=C[i][j];
}
void build(int p,int l,int r){
if (l==r){
t[p][][]=t[p][][]=t[p][][]=;t[p][][]=;
return;
}
int mid=l+r>>;
build(lp,l,mid);build(rp,mid+,r);
cc(t[lp],t[rp],t[p]);
}
void ask(int p,int l,int r,int k){
if (k<l) return;
if (r<=k){
cc(Mavis,t[p],Mavis);
return;
}
int mid=l+r>>;
ask(lp,l,mid,k);ask(rp,mid+,r,k);
}
void cg(int p,int l,int r,int k){
if (l==r){
t[p][][]=t[p][][]=t[p][][]=;t[p][][]=;
return;
}
int mid=l+r>>;
if (k<=mid) cg(lp,l,mid,k);else cg(rp,mid+,r,k);
cc(t[lp],t[rp],t[p]);
}
int main(){
n=read();
for (int i=;i<=n;i++) a[i]=read(),b[i]=i;
sort(b+,b++n,cmp);
for (int i=;i<=n;i++) a[b[i]]=i; build(,,n);
for (int i=;i<=n;i++){
Mavis[][]=Mavis[][]=;Mavis[][]=Mavis[][]=;
if (a[i]-) ask(,,n,a[i]-);
M(mmh+=Mavis[][]);M(mmh+=Mavis[][]);
cg(,,n,a[i]);
}
M(mmh-=n);
printf("%d\n",mmh);
}