QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771929 | #7219. The Mighty Spell | Symbolize | WA | 2ms | 8096kb | C++20 | 3.9kb | 2024-11-22 16:20:39 | 2024-11-22 16:20:40 |
Judging History
answer
/*
Luogu name: Symbolize
Luogu uid: 672793
*/
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=2e5+2;
const int M=50+2;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
using namespace std;
int n,m,a[N],f[N],g[N],last[N],pre[N],cnt[N][M],id[N],d[N],prod[N];
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> inline void read(T &x) {
x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
}
int v[M],tot;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
prod[0]=1;
rep1(i,1,n)
{
read(a[i]);
pre[i]=last[a[i]];
last[a[i]]=i;
memcpy(cnt[i],cnt[i-1],sizeof cnt[i-1]);
++cnt[i][a[i]];
prod[i]=1ll*prod[i-1]*2%mod;
f[i]=(1ll*2*i*i*i+1ll*3*i*i+3ll*i+3)%mod;
g[i]=((f[i]-1ll*2*f[i-1]+f[i-2])%mod+mod)%mod;
}
g[1]=f[1];
pre[n+1]=n+1;
rep1(i,1,m) id[i]=n+1;
rep2(i,n,1)
{
tot=0;
id[a[i]]=i;
rep1(j,1,m) if(pre[id[j]]<=i) v[++tot]=id[j];
v[++tot]=n+1;
stable_sort(v+1,v+1+tot);
static bool vis[M];
memset(vis,0,sizeof vis);
rep1(j,1,tot-1)
{
int ip=v[j];
vis[a[ip]]=1;
int ans=prod[ip-i+1];
rep1(k,1,m) ans=1ll*ans*(prod[cnt[i-1][k]+(cnt[n][k]-cnt[ip][k])]-(!vis[k]))%mod;
d[ip-i+1]=d[ip-i+1]+ans;
d[v[j+1]-i+1]=(d[v[j+1]-i+1]-ans+mod)%mod;
}
}
int ans=0,inv=1;
rep1(i,1,n)
{
d[i]=(d[i]+d[i-1])%mod;
inv=1ll*inv*500000004%mod;
ans=(ans+1ll*d[i]*g[i]%mod*inv%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6044kb
input:
3 2 1 2 2
output:
152
result:
ok answer is '152'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4 3 1 2 1 2
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5996kb
input:
6 3 1 2 3 3 2 1
output:
3627
result:
ok answer is '3627'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
5 5 1 4 5 3 2
output:
343
result:
ok answer is '343'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
5 5 1 5 4 3 2
output:
343
result:
ok answer is '343'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
5 5 3 1 5 4 2
output:
343
result:
ok answer is '343'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7968kb
input:
5 5 4 1 2 3 5
output:
343
result:
ok answer is '343'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
5 5 2 3 2 2 2
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
5 5 1 2 2 2 5
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7912kb
input:
5 5 4 2 1 3 5
output:
343
result:
ok answer is '343'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7984kb
input:
5 5 2 3 4 5 1
output:
343
result:
ok answer is '343'
Test #12:
score: 0
Accepted
time: 0ms
memory: 5880kb
input:
5 5 4 3 5 2 1
output:
343
result:
ok answer is '343'
Test #13:
score: 0
Accepted
time: 0ms
memory: 7904kb
input:
5 5 3 4 5 2 1
output:
343
result:
ok answer is '343'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
5 5 4 3 3 5 2
output:
0
result:
ok answer is '0'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
5 5 1 4 4 1 1
output:
0
result:
ok answer is '0'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
5 5 1 5 2 4 3
output:
343
result:
ok answer is '343'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
5 5 4 2 5 3 1
output:
343
result:
ok answer is '343'
Test #18:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
5 5 3 1 4 5 2
output:
343
result:
ok answer is '343'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5984kb
input:
5 5 5 1 3 4 2
output:
343
result:
ok answer is '343'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
5 5 4 5 3 5 5
output:
0
result:
ok answer is '0'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
5 5 2 2 3 4 2
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
5 5 4 5 1 2 3
output:
343
result:
ok answer is '343'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
5 5 3 5 1 2 4
output:
343
result:
ok answer is '343'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 5 5 4 1 2 3
output:
343
result:
ok answer is '343'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
5 5 5 3 4 1 2
output:
343
result:
ok answer is '343'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
5 5 3 1 2 1 5
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
5 5 3 1 4 2 5
output:
343
result:
ok answer is '343'
Test #28:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
5 5 1 2 4 5 3
output:
343
result:
ok answer is '343'
Test #29:
score: 0
Accepted
time: 1ms
memory: 5904kb
input:
5 5 4 3 1 5 2
output:
343
result:
ok answer is '343'
Test #30:
score: 0
Accepted
time: 1ms
memory: 7900kb
input:
5 5 2 1 3 4 5
output:
343
result:
ok answer is '343'
Test #31:
score: 0
Accepted
time: 1ms
memory: 5864kb
input:
5 5 4 2 1 3 5
output:
343
result:
ok answer is '343'
Test #32:
score: 0
Accepted
time: 0ms
memory: 5936kb
input:
5 5 4 3 1 4 3
output:
0
result:
ok answer is '0'
Test #33:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
5 5 3 4 1 1 3
output:
0
result:
ok answer is '0'
Test #34:
score: 0
Accepted
time: 1ms
memory: 7984kb
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: 0ms
memory: 5872kb
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: 1ms
memory: 5952kb
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: 5992kb
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: 0ms
memory: 3892kb
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: 0ms
memory: 3824kb
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: 0ms
memory: 3836kb
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: 0ms
memory: 5992kb
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: 7952kb
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: 5876kb
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: 6056kb
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: 5936kb
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: 0ms
memory: 5884kb
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: 0ms
memory: 5984kb
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: 0ms
memory: 5936kb
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: 5868kb
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: 0ms
memory: 5888kb
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: 3952kb
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: 5892kb
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: 0ms
memory: 5888kb
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: 5876kb
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: 8096kb
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: 5944kb
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: 0ms
memory: 3816kb
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: 2ms
memory: 7912kb
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: 5920kb
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: 0ms
memory: 5940kb
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: 5820kb
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: 5856kb
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: 5996kb
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: 8068kb
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:
459607578
result:
wrong answer expected '255072751', found '459607578'