QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771148 | #7219. The Mighty Spell | ASnown | WA | 1ms | 8156kb | C++17 | 4.8kb | 2024-11-22 10:09:58 | 2024-11-22 10:09:58 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
using i32=int32_t;
using u32=uint32_t;
using i64=int64_t;
using u64=uint64_t;
using i128=__int128_t;
using u128=__uint128_t;
constexpr i32 inverse(i32 a,i32 m) {
i64 r=1;
while(a>1) { r=r*(m-m/a)%m,a=m%a; }
return r;
}
template<i32 m>
class static_modint {
using mint=static_modint;
public:
constexpr static_modint() : v(0) {}
constexpr static_modint(i32 v) : v(normal(v%m)) {}
constexpr static_modint(u32 v) : v(v%m) {}
constexpr static_modint(i64 v) : v(normal(v%m)) {}
constexpr static_modint(u64 v) : v(v%m) {}
constexpr static_modint(i128 v) : v(normal(v%m)) {}
constexpr static_modint(u128 v) : v(v%m) {}
constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
constexpr u32 val() const { return v; }
constexpr static u32 mod() { return m; }
constexpr explicit operator bool() const { return v; }
constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
constexpr mint pow(i64 b) const { assert(b>=0);
mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint()-*this; }
constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
constexpr mint& operator++() { return (*this)+=1; }
constexpr mint& operator--() { return (*this)-=1; }
constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
constexpr friend mint operator++(mint &v,i32) { auto tmp=v; v+=1; return tmp; }
constexpr friend mint operator--(mint &v,i32) { auto tmp=v; v-=1; return tmp; }
constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
constexpr bool operator==(const mint& p) const { return val()==p.val(); }
constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
using mint=asnown::modint107;
const int N = 2e5+25,M = 55;
int n,m;
int a[N];
mint f[N],g[N];
int pre[M],bot[M];
int cnt[N][M];
mint ans[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Solve();
}
void Solve() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
mint x=i;
f[i]=2*x*x*x+3*x*x+3*x+3;
}
g[1]=f[1];
for(int i=2;i<=n;i++) g[i]=f[i]-2*f[i-1]+f[i-2];
for(int i=1;i<=n;i++) {
cin>>a[i];
pre[i]=bot[a[i]];
bot[a[i]]=i;
memcpy(cnt[i],cnt[i-1],sizeof cnt[i]);
++cnt[i][a[i]];
} pre[n+1]=n+1;
for(int i=1;i<=m;i++) bot[i]=n+1;
for(int l=n;l>=1;l--) {
vector<int> r;
bot[a[l]]=l;
for(int i=1;i<=m;i++) if(pre[bot[i]]<=l)
r.emplace_back(bot[i]);
r.emplace_back(n+1);
sort(ALL(r));
static mint tmp[M]; memset(tmp,0,sizeof tmp);
static bool vis[M]; memset(vis,0,sizeof vis);
for(int i=1;i<=m;i++) tmp[i]=mint(2).pow(cnt[l-1][i]+cnt[n][i]-cnt[l][i])-1;
for(int i=0;i+1<r.size();i++) {
vis[a[r[i]]]=true;
mint res=1;
for(int x=1;x<=m;x++) res*=mint(2).pow(cnt[l-1][x]+cnt[n][x]-cnt[r[i]][x])-(!vis[x]);
res*=mint(2).pow(r[i]-l+1);
ans[r[i]-l+1]+=res,ans[r[i+1]-l+1]-=res;
}
}
mint sum=0;
for(int i=1;i<=n;i++) {
ans[i]+=ans[i-1];
sum+=ans[i]*g[i]/(mint(2).pow(i));
}
printf("%d\n",sum.val());
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5924kb
input:
3 2 1 2 2
output:
152
result:
ok answer is '152'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
4 3 1 2 1 2
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
6 3 1 2 3 3 2 1
output:
3627
result:
ok answer is '3627'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6112kb
input:
5 5 1 4 5 3 2
output:
343
result:
ok answer is '343'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
5 5 1 5 4 3 2
output:
343
result:
ok answer is '343'
Test #6:
score: 0
Accepted
time: 0ms
memory: 6084kb
input:
5 5 3 1 5 4 2
output:
343
result:
ok answer is '343'
Test #7:
score: 0
Accepted
time: 1ms
memory: 6104kb
input:
5 5 4 1 2 3 5
output:
343
result:
ok answer is '343'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5780kb
input:
5 5 2 3 2 2 2
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6108kb
input:
5 5 1 2 2 2 5
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
5 5 4 2 1 3 5
output:
343
result:
ok answer is '343'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5764kb
input:
5 5 2 3 4 5 1
output:
343
result:
ok answer is '343'
Test #12:
score: 0
Accepted
time: 0ms
memory: 5832kb
input:
5 5 4 3 5 2 1
output:
343
result:
ok answer is '343'
Test #13:
score: 0
Accepted
time: 1ms
memory: 6108kb
input:
5 5 3 4 5 2 1
output:
343
result:
ok answer is '343'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
5 5 4 3 3 5 2
output:
0
result:
ok answer is '0'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
5 5 1 4 4 1 1
output:
0
result:
ok answer is '0'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
5 5 1 5 2 4 3
output:
343
result:
ok answer is '343'
Test #17:
score: 0
Accepted
time: 0ms
memory: 6080kb
input:
5 5 4 2 5 3 1
output:
343
result:
ok answer is '343'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5824kb
input:
5 5 3 1 4 5 2
output:
343
result:
ok answer is '343'
Test #19:
score: 0
Accepted
time: 1ms
memory: 6080kb
input:
5 5 5 1 3 4 2
output:
343
result:
ok answer is '343'
Test #20:
score: 0
Accepted
time: 0ms
memory: 5848kb
input:
5 5 4 5 3 5 5
output:
0
result:
ok answer is '0'
Test #21:
score: 0
Accepted
time: 1ms
memory: 6192kb
input:
5 5 2 2 3 4 2
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
5 5 4 5 1 2 3
output:
343
result:
ok answer is '343'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
5 5 3 5 1 2 4
output:
343
result:
ok answer is '343'
Test #24:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
5 5 5 4 1 2 3
output:
343
result:
ok answer is '343'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
5 5 5 3 4 1 2
output:
343
result:
ok answer is '343'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
5 5 3 1 2 1 5
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
5 5 3 1 4 2 5
output:
343
result:
ok answer is '343'
Test #28:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
5 5 1 2 4 5 3
output:
343
result:
ok answer is '343'
Test #29:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
5 5 4 3 1 5 2
output:
343
result:
ok answer is '343'
Test #30:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
5 5 2 1 3 4 5
output:
343
result:
ok answer is '343'
Test #31:
score: 0
Accepted
time: 1ms
memory: 6192kb
input:
5 5 4 2 1 3 5
output:
343
result:
ok answer is '343'
Test #32:
score: 0
Accepted
time: 0ms
memory: 6104kb
input:
5 5 4 3 1 4 3
output:
0
result:
ok answer is '0'
Test #33:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
5 5 3 4 1 1 3
output:
0
result:
ok answer is '0'
Test #34:
score: 0
Accepted
time: 0ms
memory: 7932kb
input:
20 5 5 2 5 1 5 5 2 4 5 5 2 5 5 5 5 4 2 5 3 4
output:
102882880
result:
ok answer is '102882880'
Test #35:
score: 0
Accepted
time: 1ms
memory: 7864kb
input:
20 5 3 2 1 2 2 2 2 2 4 3 2 2 3 3 5 2 2 1 2 5
output:
134653185
result:
ok answer is '134653185'
Test #36:
score: 0
Accepted
time: 0ms
memory: 8156kb
input:
20 5 1 2 3 2 1 3 5 1 2 4 5 2 3 4 5 1 4 3 4 5
output:
315505338
result:
ok answer is '315505338'
Test #37:
score: 0
Accepted
time: 1ms
memory: 5860kb
input:
20 5 5 2 2 4 2 3 5 1 1 3 1 5 2 4 4 3 1 4 3 5
output:
312062382
result:
ok answer is '312062382'
Test #38:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
20 5 3 4 2 5 4 5 5 4 1 4 3 3 4 3 4 2 3 2 5 3
output:
188515821
result:
ok answer is '188515821'
Test #39:
score: 0
Accepted
time: 1ms
memory: 7964kb
input:
20 5 3 5 1 3 3 4 5 2 1 1 3 1 2 5 2 1 1 2 5 2
output:
197857329
result:
ok answer is '197857329'
Test #40:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
20 10 3 8 6 8 9 2 1 5 8 6 7 8 4 8 6 8 10 8 8 8
output:
4905343
result:
ok answer is '4905343'
Test #41:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
20 10 10 5 1 8 7 2 7 2 6 2 2 2 2 2 4 2 3 7 9 7
output:
3724041
result:
ok answer is '3724041'
Test #42:
score: 0
Accepted
time: 1ms
memory: 6192kb
input:
20 10 5 1 9 6 10 4 5 3 2 4 8 3 7 1 8 6 2 9 10 7
output:
52978806
result:
ok answer is '52978806'
Test #43:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
20 10 5 8 6 2 1 10 3 8 9 7 6 5 10 9 1 7 3 4 4 2
output:
53309955
result:
ok answer is '53309955'
Test #44:
score: 0
Accepted
time: 1ms
memory: 7868kb
input:
20 10 1 8 1 7 9 7 9 9 7 4 1 6 2 7 8 6 6 9 6 7
output:
0
result:
ok answer is '0'
Test #45:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
20 10 1 10 10 10 2 9 1 1 7 2 3 9 5 10 8 4 1 4 2 5
output:
0
result:
ok answer is '0'
Test #46:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
20 20 9 16 3 18 8 19 6 4 2 17 1 15 10 11 5 13 12 7 14 20
output:
17263
result:
ok answer is '17263'
Test #47:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
20 20 2 17 18 12 15 20 11 9 10 5 6 16 7 8 4 13 3 1 19 14
output:
17263
result:
ok answer is '17263'
Test #48:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
20 20 14 15 19 8 3 20 9 12 18 7 5 11 4 2 16 6 1 17 10 13
output:
17263
result:
ok answer is '17263'
Test #49:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
20 20 18 9 3 4 13 12 15 11 2 16 19 7 10 20 17 8 6 1 14 5
output:
17263
result:
ok answer is '17263'
Test #50:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
20 20 7 6 4 14 20 13 1 15 5 18 16 10 1 16 12 14 5 13 1 3
output:
0
result:
ok answer is '0'
Test #51:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
20 20 17 17 5 16 9 14 14 1 2 4 19 8 9 5 9 20 5 16 20 9
output:
0
result:
ok answer is '0'
Test #52:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
20 20 20 1 16 5 19 11 8 7 2 3 12 6 17 14 13 18 4 10 15 9
output:
17263
result:
ok answer is '17263'
Test #53:
score: 0
Accepted
time: 1ms
memory: 6112kb
input:
20 20 2 13 6 1 17 3 11 9 8 10 7 5 16 14 4 15 18 19 20 12
output:
17263
result:
ok answer is '17263'
Test #54:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
20 20 17 11 13 5 2 14 18 7 6 9 10 3 16 15 8 1 19 4 12 20
output:
17263
result:
ok answer is '17263'
Test #55:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
20 20 7 13 1 15 9 2 8 20 4 5 12 3 11 14 10 18 6 17 16 19
output:
17263
result:
ok answer is '17263'
Test #56:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
20 20 11 8 17 7 10 20 20 12 7 3 7 14 15 4 14 7 11 1 12 20
output:
0
result:
ok answer is '0'
Test #57:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
20 20 20 18 17 14 11 2 13 3 10 1 16 3 1 16 10 8 4 8 13 3
output:
0
result:
ok answer is '0'
Test #58:
score: 0
Accepted
time: 1ms
memory: 7928kb
input:
20 20 1 20 7 4 18 11 9 8 3 6 16 13 19 2 12 14 15 17 10 5
output:
17263
result:
ok answer is '17263'
Test #59:
score: 0
Accepted
time: 1ms
memory: 6196kb
input:
20 20 8 4 5 18 16 15 19 2 13 1 14 7 10 12 17 3 6 9 20 11
output:
17263
result:
ok answer is '17263'
Test #60:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
20 20 13 14 8 9 18 17 20 6 15 3 2 16 12 11 1 10 19 4 7 5
output:
17263
result:
ok answer is '17263'
Test #61:
score: 0
Accepted
time: 1ms
memory: 6112kb
input:
20 20 4 10 17 8 19 1 16 3 14 6 7 11 13 15 20 9 12 5 2 18
output:
17263
result:
ok answer is '17263'
Test #62:
score: 0
Accepted
time: 1ms
memory: 6204kb
input:
20 20 19 17 19 8 7 1 18 13 16 16 20 11 5 8 17 19 11 14 4 8
output:
0
result:
ok answer is '0'
Test #63:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
20 20 7 1 14 13 20 16 10 18 16 12 5 7 16 14 6 12 11 20 10 19
output:
0
result:
ok answer is '0'
Test #64:
score: -100
Wrong Answer
time: 0ms
memory: 5944kb
input:
500 5 3 5 5 3 5 3 5 5 3 3 3 3 3 3 1 3 3 3 3 3 3 3 5 3 3 3 1 3 3 3 3 5 3 3 3 3 3 3 3 3 3 3 5 3 3 3 5 3 3 5 2 3 3 3 5 3 3 3 3 1 3 3 5 3 3 5 3 3 5 3 5 3 3 3 3 3 3 5 3 5 3 3 5 3 5 3 5 3 3 3 3 3 3 3 3 3 3 3 3 3 5 3 3 3 3 3 3 3 3 3 3 3 5 3 3 3 3 3 3 3 5 3 3 5 5 3 3 3 3 3 5 3 5 3 3 3 3 5 3 3 3 3 3 3 3 3 3 ...
output:
781121188
result:
wrong answer expected '255072751', found '781121188'