Submission #3602053
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define maxn 25020
#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int> pr;
const ll mod = 1e9 + 7;
int a[maxn],n,m,k,vis[maxn];
ll sum[420],f[maxn][420],g[maxn][420],fac[maxn],totl[maxn],totr[maxn],sum2[420];
inline ll power(ll x,ll y){
ll res = 1;
while ( y ){
if ( y & 1 ) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
inline void up(ll &x,ll y){ x = (x + y + mod) % mod; }
int main(){
scanf("%d %d %d",&n,&k,&m);
rep(i,1,m) scanf("%d",&a[i]);
int lmx = m,rmx = m,mx = 0,last = 1;
fac[0] = 1;
rep(i,1,k) fac[i] = fac[i - 1] * i % mod;
rep(i,1,m){
if ( vis[a[i]] ){ lmx = i - 1; break; }
vis[a[i]] = 1;
}
repd(i,m,1){
if ( vis[a[i]] == 2 ){ rmx = m - i; break; }
vis[a[i]] = 2;
}
rep(i,1,k) vis[i] = 0;
rep(i,1,m){
if ( vis[a[i]] ){
mx = max(mx,i - last);
last = vis[a[i]] + 1;
}
vis[a[i]] = i;
}
mx = max(mx,m - last + 1);
ll ans = power(k,n - m) * (n - m + 1) % mod;
if ( mx == k ) cout<<ans<<endl;
else if ( lmx == m ){
f[0][0] = 1;
rep(i,1,n){
rep(j,1,k){
sum[j] = (sum[j - 1] + f[i - 1][j]) % mod;
sum2[j] = (sum2[j - 1] + g[i - 1][j]) % mod;
}
rep(j,1,k - 1){
f[i][j] = (f[i - 1][j - 1] * (k - j + 1) + sum[k - 1] - sum[j - 1] + mod) % mod;
g[i][j] = (g[i - 1][j - 1] * (k - j + 1) + sum2[k - 1] - sum2[j - 1] + mod) % mod;
if ( j >= m ) up(g[i][j],f[i][j]);
}
}
ll tmp = 0;
rep(i,1,k - 1) up(tmp,g[n][i]);
tmp = tmp * fac[k - m] % mod * power(fac[k],mod - 2) % mod;
up(ans,-tmp);
cout<<ans<<endl;
}
else{
f[lmx][lmx] = 1;
rep(i,lmx + 1,n){
rep(j,1,k) sum[j] = (sum[j - 1] + f[i - 1][j]) % mod;
rep(j,1,k - 1){
f[i][j] = (f[i - 1][j - 1] * (k - j + 1) + sum[k - 1] - sum[j - 1] + mod) % mod;
}
}
rep(i,lmx,n){
rep(j,1,k - 1) up(totl[i],f[i][j]);
}
rep(i,0,n) rep(j,0,k) f[i][j] = 0;
memset(sum,0,sizeof(sum));
f[rmx][rmx] = 1;
rep(i,rmx + 1,n){
rep(j,1,k) sum[j] = (sum[j - 1] + f[i - 1][j]) % mod;
rep(j,1,k - 1){
f[i][j] = (f[i - 1][j - 1] * (k - j + 1) + sum[k - 1] - sum[j - 1] + mod) % mod;
}
}
rep(i,rmx,n){
rep(j,1,k - 1) up(totr[i],f[i][j]);
}
rep(i,lmx,n){
int r = n - i - (m - lmx - rmx);
if ( r < rmx ) break;
up(ans,-totr[r] * totl[i] % mod);
}
cout<<ans<<endl;
}
}
Submission Info
Submission Time |
|
Task |
F - Colorful Sequences |
User |
zhangqingqi |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2883 Byte |
Status |
WA |
Exec Time |
278 ms |
Memory |
164352 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:34:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&k,&m);
^
./Main.cpp:35:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,1,m) scanf("%d",&a[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt, sample_07.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt, sample_07.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt, sample_07.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
2304 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
2 ms |
2304 KB |
sample_04.txt |
AC |
2 ms |
2304 KB |
sample_05.txt |
AC |
1 ms |
256 KB |
sample_06.txt |
AC |
159 ms |
164352 KB |
sample_07.txt |
AC |
89 ms |
35200 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
2 ms |
2432 KB |
subtask_1_03.txt |
AC |
2 ms |
2432 KB |
subtask_1_04.txt |
WA |
2 ms |
2304 KB |
subtask_1_05.txt |
AC |
3 ms |
2304 KB |
subtask_1_06.txt |
AC |
276 ms |
83456 KB |
subtask_1_07.txt |
AC |
156 ms |
164352 KB |
subtask_1_08.txt |
AC |
1 ms |
256 KB |
subtask_1_09.txt |
AC |
276 ms |
83456 KB |
subtask_1_10.txt |
AC |
37 ms |
14720 KB |
subtask_1_11.txt |
AC |
13 ms |
28288 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
63 ms |
39296 KB |
subtask_1_14.txt |
AC |
276 ms |
83456 KB |
subtask_1_15.txt |
AC |
153 ms |
164352 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |
subtask_1_17.txt |
AC |
274 ms |
83456 KB |
subtask_1_18.txt |
AC |
257 ms |
80512 KB |
subtask_1_19.txt |
AC |
1 ms |
256 KB |
subtask_1_20.txt |
WA |
4 ms |
4352 KB |
subtask_1_21.txt |
AC |
85 ms |
51712 KB |
subtask_1_22.txt |
AC |
276 ms |
83456 KB |
subtask_1_23.txt |
AC |
1 ms |
256 KB |
subtask_1_24.txt |
WA |
276 ms |
83456 KB |
subtask_1_25.txt |
AC |
274 ms |
83456 KB |
subtask_1_26.txt |
AC |
278 ms |
83584 KB |
subtask_1_27.txt |
AC |
1 ms |
256 KB |
subtask_1_28.txt |
WA |
277 ms |
83456 KB |
subtask_1_29.txt |
AC |
278 ms |
83456 KB |
subtask_1_30.txt |
AC |
278 ms |
83584 KB |
subtask_1_31.txt |
AC |
1 ms |
256 KB |
subtask_1_32.txt |
WA |
278 ms |
83584 KB |
subtask_1_33.txt |
AC |
274 ms |
83456 KB |