【BZOJ4731】【清华集训2016】魔法小程序

BZOJ数据有问题气啊

就是给你一个\(k\)维前缀和，让你还原每个元素

每一维相应的减一遍就可以了

// <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;
}

// <4731.cpp> - Thu Mar 9 15:37:02 2017

// This file is created by XuYike's black technology automatically.

// 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;

}