@KirinBill
2017-10-15T15:27:01.000000Z
字数 3025
阅读 1127
题解
套题
目录
#include <cstdio>
#include <algorithm>
using std::min;
inline int pow(int x,int y,int p){
int ret=1;
for(;y;y>>=1,x=(long long)x*x%p){
if(y&1) ret=(long long)ret*x%p;
}
return ret;
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int sum=n+m;
printf("%d",min((long long)n*pow(2,k,sum)%sum,(long long)m*pow(2,k,sum)%sum));
return 0;
}
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::min;
const int MAXN=1e5+5;
int n,k;
int a[MAXN],pos[MAXN],nex[MAXN];
inline int find(int tmp,int pos){
if(tmp<0) return n+1;
else if(tmp==0) return nex[pos];
int ret=n+1;
for(int i=1;i*i<=tmp;++i){
if(tmp%i==0){
if(i>k) ret=min(ret,::pos[i]);
if(tmp/i>k) ret=min(ret,::pos[tmp/i]);
}
}
return ret;
}
inline int solve(){
static int y[MAXN];
nex[n+1]=n+1;
for(int i=n;i;--i)
nex[i]= a[i]>k ? i:nex[i+1];
memset(pos,0x7f,sizeof(pos));
for(int i=n;i;--i){
y[i]=find(a[i]-k,i);
pos[a[i]]=i;
}
long long ret=0;
for(int i=n,miny=n+1;i;--i){
miny=min(miny,y[i]);
ret+=miny-i;
}
return ret;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
printf("%lld",solve());
return 0;
}
#include <cstdio>
const int MAXN=1e6+5,MAXA=5005,MAXM=MAXN;
int n,m,P;
int a[MAXN],fac[MAXA],A[MAXM],f[MAXA][MAXA];
//A(i,i)=i!,A(i)=A(m,i)
inline void pre_tab(){
A[0]=1;
for(int i=1;i<=m;++i)
A[i]=(long long)A[i-1]*(m-i+1)%P;
fac[0]=1;
for(int i=1;i<MAXA;++i)
fac[i]=(long long)fac[i-1]*i%P;
f[0][0]=1;
for(int i=1;i<MAXA;++i){
for(int j=1;j<=i;++j)
f[i][j]=((long long)f[i-1][j]*(j-1)%P+f[i-1][j-1])%P;
}
}
inline int DP(){
static int dp[2][MAXA];
//dp[0/1][0]=sum
dp[0][0]=1;
for(int i=1;i<=n;++i){
dp[i&1][0]=0;
for(int j=1;j<=a[i];++j){
dp[i&1][j]=(long long)A[j]*f[a[i]][j]%P*dp[~i&1][0]%P;
if(j<=a[i-1])
dp[i&1][j]=(dp[i&1][j]-(long long)fac[j]*f[a[i]][j]%P*dp[~i&1][j]%P+P)%P;
dp[i&1][0]=(dp[i&1][0]+dp[i&1][j])%P;
}
}
return dp[n&1][0];
}
int main(){
scanf("%d%d%d",&n,&m,&P);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
pre_tab();
printf("%d",DP());
return 0;
}