BZOJ数据有问题 气啊
就是给你一个\(k\)维前缀和,让你还原每个元素
每一维相应的减一遍就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// <4731.cpp> - Thu Mar 9 15:37:02 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=1000010; const int INF=1e9; int a[MAXN],c[MAXN]; int main(){ int m=gi();for(int i=0;i<m;i++)a[i]=gi();a[m]=INF; int n=gi();for(int i=0;i<n;i++)c[i]=gi(); for(int i=0,mi=1;i<=m;i++){ if(a[i]==1)continue; for(int j=n-1;j>=0;j--) if(j/mi%a[i])c[j]-=c[j-mi]; if((mi*=a[i])>n)break; } printf("%d\n",m);for(int i=0;i<m;i++)printf("%d ",a[i]); printf("\n%d\n",n);for(int i=0;i<n;i++)printf("%d ",c[i]); return 0; } |