B. Wonderful Array

Wonderful Array"/>

B. Wonderful Array

                                                        B. Wonderful Array

Problem - B - Codeforces

思路：我们需要求的是bi<=bi+1的个数，对于i=[0,n-1]，我们求这个个数其实是不好求的，即使是=的个数就是求有多少个位置b[i]%m==0，好像也不是那么容易求得，所以我们可以考虑一下，如果我们能够求出来>的个数，那么其实就是可以求出来<=的个数了，首先x跟b0,b1,...,bn-1如果是大于m的，那么其实只有对m的余数是有用的，所以我们可以对x,b0,b1....bn-1都对m取余，而着就出现了一个有趣的问题，如果我们从头开始计算直到计算到bn，假设当前是第i个，并且i-1的值为res，那么当前的值为res+a[i%k]，那么有趣的现象来了，如果这个值是比m大的，那么它在对m取模之后是一定比res小的，因为我们加上的这个数a[i%k]是比m小的，所以这个结果是res%m>(res+a[i%k])%m，所以这是一个>的合法解，然后我们又发现了，只要我们找到了所有的这种情况，那么其实就是>的所有的解，而又有一个有趣的事，因为我们每次加的都是比m小的，所以只要bn中有几个m的倍数，就会出现几个这种>情况，所以我们只需要求出来bn是多少，然后除m就是>的情况，所以n-bn/m就是<=的情况

// Problem: B. Wonderful Array
// Contest: Codeforces - 2023 (ICPC) Jiangxi Provincial Contest -- Official Contest
// URL: 
// Memory Limit: 512 MB
// Time Limit: 1000 ms#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<vector> 
#include<set>
#include<unordered_map>
#include<ctime>
#include<cstdlib>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef pair<int,pair<int,int> > PIII;
const double eps=1e-7;
const int N=1e6+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}int T,hackT;
int n,m,k;
ll w[N];
int vis[N];void solve() {k=read();for(int i=0;i<k;i++) vis[i]=read();n=read(),m=read();int x=read();x=x%m;for(int i=0;i<k;i++) vis[i]=vis[i]%m;w[0]=x;for(int i=1;i<=k;i++) w[i]=w[i-1]+vis[i-1];int t=(n/k)*k;ll sum=w[k]-w[0];ll res=(ll)sum*(n/k)+x;for(int i=t+1;i<=n;i++) res+=vis[i-t-1];int ans=n-res/m;printf("%d\n",ans);
}   int main() {// init();// stin();// scanf("%d",&T);T=1; while(T--) hackT++,solve();return 0;       
}