问题标题: 酷町堂：5220RE找错

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

 

typedef long long ll;

const int Maxn = 4e7;

 

struct BigInteger {

static const int BASE = 100000000;

int num[15], len;

BigInteger (ll x = 0) {

*this = x;

}

inline void clear(BigInteger &x) {

while(x.num[x.len] == 0 && x.len > 1)

x.len--;

}

BigInteger operator = (ll rhs) {

memset(num, 0, sizeof num);

len = 0;

do {

num[++len] = rhs % BASE;

rhs /= BASE;

} while(rhs != 0);

return *this;

}

BigInteger operator + (const BigInteger &rhs) {

BigInteger ret;

memset(ret.num, 0, sizeof ret.num), ret.len = 0;

for(int i = 1, tmp = 0; tmp != 0 || i <= len || i <= rhs.len; i++) {

tmp += num[i] + rhs.num[i];

ret.num[++ret.len] = tmp % BASE;

tmp /= BASE;

}

return ret;

}

BigInteger operator * (const BigInteger &rhs) {

BigInteger ret;

memset(ret.num, 0, sizeof ret.num), ret.len = len + rhs.len;

for(int i = 1; i <= len; i++) {

ll tmp = 0;

for(int j = 1; j <= rhs.len || tmp != 0; j++) {

tmp += 1LL * num[i] * rhs.num[j] + ret.num[i + j - 1];

ret.num[i + j - 1] = tmp % BASE;

tmp /= BASE;

}

}

clear(ret);

return ret;

}

BigInteger operator += (const BigInteger &rhs) {

*this = *this + rhs;

return *this;

}

BigInteger operator *= (const BigInteger &rhs) {

*this = *this * rhs;

return *this;

}

};

ostream &operator << (ostream &out, const BigInteger &x) {

out << x.num[x.len];

for(int i = x.len - 1; i >= 1; i--) {

char buf[20];

sprintf(buf, "%08d", x.num[i]);

out << buf;

}

return out;

}

 

int N;

ll sum[Maxn + 5];

 

ll B[Maxn + 5];

const ll mod = (1 << 30);

 

inline void ReadIn() {

int typ;

scanf("%d %d", &N, &typ);

if(typ == 0) {

for(int i = 1; i <= N; i++)

scanf("%lld", &sum[i]);

} else {

ll x, y, z;

scanf("%lld %lld %lld %lld %lld", &x, &y, &z, &B[1], &B[2]);

for(int i = 3; i <= N; i++)

B[i] = ((x * B[i - 1] % mod) + (y * B[i - 2] % mod) + z) % mod;

int m, las = 0, p;

scanf("%d", &m);

for(int i = 1; i <= m; i++) {

int l, r;

scanf("%d %d %d", &p, &l, &r);

for(int j = las + 1; j <= p; j++)

sum[j] = (B[j] % (r - l + 1)) + l;

las = p;

}

}

}

 

int f[Maxn + 5];

inline ll calc_val(int pos) {

return sum[pos] * 2 - sum[f[pos]];

}

 

int q[Maxn + 5], head, tail;

 

int main() {

#ifdef LOACL

freopen("in.txt", "r", stdin);

freopen("out.txt", "w", stdout);

#endif

ReadIn();

for(int i = 1; i <= N; i++)

sum[i] += sum[i - 1];

head = tail = 1;

for(int i = 1; i <= N; i++) {

while(head < tail && calc_val(q[head + 1]) <= sum[i])

head++;

f[i] = q[head];

while(head <= tail && calc_val(q[tail]) >= calc_val(i))

tail--;

q[++tail] = i;

}

BigInteger ans = 0;

int p = N;

while(p != 0) {

BigInteger tmp(sum[p] - sum[f[p]]);

ans += (tmp * tmp);

p = f[p];

}

cout << ans;

return 0;

}

李秉轩在2020-09-09 20:18:15追加了内容

• 七星级题代码

• #define N 103
  #define M 2003
  #define ac(x) (((x)+N))
  #define ll long long
  #define setIO(s) freopen(s".in","r",stdin)
  using namespace std;
  const int mod=998244353;
  ll sum[N];
  int a[N][M],g[N][N],f[N][N+N+233];
  int main()
  {
  // setIO("input");
  ll ans=0ll;
  int i,j,n,m,k;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%d",&a[i][j]), (sum[i]+=1ll*a[i][j])%=mod;
  g[0][0]=1, f[0][ac(0)]=1;
  for(i=1;i<=n;++i)
  {
  for(j=0;j<=i;++j)
  {
  g[i][j]=g[i-1][j];
  if(j>0) g[i][j]=(g[i][j]+1ll*g[i-1][j-1]*sum[i]%mod)%mod;
  }
  }
  for(i=1;i<=n;++i) (ans+=g[n][i])%=mod;
  for(int tmp=1;tmp<=m;++tmp)
  {
  for(i=1;i<=n;++i)
  {
  for(j=-i;j<=i;++j)
  {
  f[i][ac(j)]=f[i-1][ac(j)];
  if(j<i) (f[i][ac(j)]+=1ll*f[i-1][ac(j)+1]*(sum[i]-a[i][tmp])%mod)%=mod;
  if(j>-i) (f[i][ac(j)]+=1ll*f[i-1][ac(j)-1]*a[i][tmp]%mod)%=mod;
  }
  }
  for(i=1;i<=n;++i) ((ans-=f[n][ac(i)])+=mod)%=mod;
  for(i=1;i<=n;++i) for(j=-n;j<=n;++j) f[i][ac(j)]=0;
  }
  printf("%lld\n",ans);
  return 0;
  }