国庆七连测（二） 模模塔

2019-04-13 15:04发布

站内文章 / 模拟电子
15527 0 1773
（这是什么破标题）
【一句话题意】给定两个数组ai和bi，求数组ci。变换规律为ci=Σj=1i⌊ab⌋bi mod j c_{i}=Sigma^i_{j=1} lfloor frac{a}{b} floor b_{i ,mod,j}
n<=100,000 每个ci对123456789取模
【分析】
这题需要玄学 O(nsqrt{n}) 优化。
玄学打表可得：i/j的值不变时，b的下标成公差为i/j的等差序列（具体原因不明）。当 j小于等于根号i时，暴力计算；另外部分i/j的大小小于等于根号i，如果预处理好公差的等差序列前缀和也可以O1求解。
而预处理的复杂度也在O(nn) O(nsqrt{n})
所以总复杂度就在O(nn) O(nsqrt{n})
完美卡过。。。。
Code: #include #include #include #include #include using namespace std; typedef long long LL; const int maxn=1e5+1000; const int K=330; const int mod=123456789; int a[maxn],b[maxn],c[maxn]; int sum[K][maxn]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=0;i<n;i++)scanf("%d",&b[i]); for(int i=1;i<K;i++) for(int j=0;j<n;j++){ sum[i][j]=(j>=i?sum[i][j-i]:0)+b[j]; while(sum[i][j]>=mod) sum[i][j]-=mod; } for(int i=1;i<=n;i++){ for(int j=1;j<=K&&j<=i;j++) c[i]=(c[i]+(LL)a[i/j]*b[i%j])%mod; int r,t; for(int j=K+1;j<=i;j=r+1){ t=i/j,r=i/t; c[i]=(c[i]+(LL)a[t]*(mod+sum[t][i-t*j]-(i>t*(r+1)?sum[t][i-t*(r+1)]:0)))%mod; } } for(int i=1;i<=n;i++) printf("%d ",c[i]); return 0; }

热门文章