Submission #3602068

---

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 = max(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

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