牛客练习赛65水题ABINLiusy的博客-

Powered by:AB_IN 局外人

A 最值序列

纯模拟题。

mod=998244353 n=int(input()) s=list(map(int,input().split())) s.sort() if n&1:     lst=s[:n//2+1]     tmp=s[n//2+1:]     ans=1 for i in tmp:         ans=ans*i%mod     print(sum(lst)*ans*tmp[-1]%mod) else:     lst=s[:n//2]     tmp=s[n//2:]     ans=1 for i in tmp:         ans=ans*i%mod     print(sum(lst)*ans%mod) 

B 多重序列

又搞了个cost最少，跟B干上了？？

#include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) typedef unsigned long long ll; const ll maxn=1e12; using namespace std; namespace IO{ char ibuf[1<<21],*ip=ibuf,*ip_=ibuf; char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21); inline char gc(){ if(ip!=ip_)return *ip++;         ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin); return ip==ip_?EOF:*ip++; } inline void pc(char c){ if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf; *op++=c; } inline ll read(){ register ll x=0,ch=gc(),w=1; for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1; for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48; return w*x; } template<class I> inline void write(I x){ if(x<0)pc('-'),x=-x; if(x>9)write(x/10);pc(x%10+'0'); } class flusher_{ public: ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);} }IO_flusher; } using namespace IO; ll quickmod (ll a, ll b ,ll c) {     ll ret=1%c; while(b){ if(b&1)             ret=ret*a%c;         a=a*a%c;         b=b>>1; } return ret; } map<ll,int>vis; ll n,m,k,mod,x,ans,max_1=0; int main() {     n=read();m=read();k=read();mod=read(); if (k == 1) { puts("1"); return 0; } for(ll i=0,j=1;j<=maxn;i++,j*=k)         vis[j]=i; for(int i=1;i<=n;i++){         ans=0; for(int j=1;j<=m;j++){             x=read();             ans+=vis[x]; } if (ans > max_1) max_1 = ans; } write(quickmod(k,max_1,mod)); pc('n'); } 

1. 更新了读入会爆long long的bug，以后会用这个读入。

2. 注意到相乘的都是
   $k^{x}$

   kx
   那么不妨变成这样
   $k^{x1+x2+x3+…..+xm}$

   kx1+x2+x3+.....+xm
   只需要算x的和即可，之后对式子进行快速幂取模即可。

3. 那么怎么判断是不是k的非负整数次幂呢？

   可以把数值作为键，幂作为值，存入map中。这是一种非常好的思维，巧妙的运用map不会爆的性质，max_1加上这个数的下标即可。如果以数值为下标，幂为键的话，数值肯定会爆ull。
   

一直赶不上rank，一直白名。
哎。
完结。