daily 2

CF 893D

贪心，由于我们次都可以往里面打钱，所以不需要害怕<0的情况，那么我们只要管超过d的情况,我们维护一个后x天的最大balance的值，然后我们从前往后遍历，每次我们对应看当前是否要加，要加的话我们得加上后缀能够允许的钱的数量，如果加上了还是<0那么就是非法的

void solve(){
  int n,d;
  cin>>n>>d;
  vector<int>a(n+1);
  vector<ll>sum(n+1);
  vector<ll>suffix_sum(n+1);
  for(int i=1;i<=n;++i){
    cin>>a[i];
    sum[i]=sum[i-1]+a[i];
  }
  suffix_sum[n]=sum[n];
  for(int i=n-1;i>=1;--i){
    suffix_sum[i]=max(sum[i],suffix_sum[i+1]);
  }
  if(suffix_sum[1]>d){
    cout<<-1<<'\n';
    return;
  }
  ll cur=0,delta=0;
  int ans=0;
  for(int i=1;i<=n;++i){
    if(a[i]!=0){
        cur+=a[i];
    }else{//did some shit
        if(cur>=0)continue;
        ll cur_add=d-(delta+suffix_sum[i]);
        cur+=cur_add;
        delta+=cur_add;
        if(cur<0){
            cout<<-1<<'\n';
            return;
        }
        ++ans;
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 893E

傻子都知道要质因数分解,然后就是一个隔板法的问题，最后记得可以有偶数个负数，乘上二项式定理的一半即可

ll quick_pow(ll x,ll exp,int p)
{
      ll ans=1;
      while(exp)
      {
        if(exp&1)ans=ans*x%p;
        exp>>=1;
        x=x*x%p;
      }
      return ans;
}
ll inv[MAXN],fac[MAXN];
void init(int n,int p)
{
  memset(inv,0,sizeof(inv));
  memset(fac,0,sizeof(fac));
  inv[0]=fac[0]=1;
  for(int i=1;i<=n;++i)
  {
    fac[i]=fac[i-1]*i%p;
  }
  inv[n]=quick_pow(fac[n],p-2,p)%p;
  for(int i=n;i>=1;--i)inv[i-1]=inv[i]*i%p;
  for(int i=2;i<MAXN;++i){
    if(!pi[i]){
        prime.push_back(i);
    }
    for(int j=0;j<prime.size()&&prime[j]*i<MAXN;++j){
        pi[prime[j]*i]=1;
        if(i%prime[j]){
            break;
        }
    }
  }
}
ll C(ll n,ll m,ll p)
{
  if(m>n||m<0)return 0;
  return fac[n]*inv[n-m]%p*inv[m]%p;
}
void solve(){
  int x,y;
  cin>>x>>y;
  ll ans=1;
  for(int i=0;prime[i]*prime[i]<=x;++i){
    int cnt=0;
    while(x%prime[i]==0){
      x/=prime[i];
      ++cnt;
    }
    if(cnt>0)ans=(ans*C(cnt+y-1,y-1,MOD))%MOD;
  }
  if(x>1){
    ans=(ans*C(y,y-1,MOD))%MOD;
  }
  cout<<ans*quick_pow(2,y-1,MOD)%MOD<<'\n';
  return;
}