2 条题解
-
3
#include<cstdio> #include<cctype> #include<algorithm> inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x; } typedef long long int64; const int N=5001; int f[N][N],g[N][N]; int main() { const int n=getint(),m=getint(),p=getint(); f[0][0]=g[0][0]=1; for(register int i=1;i<=n;i++) { for(register int j=1;j<=std::min(i,m-1);j++) { f[i][j]=((int64)f[i-1][j-1]*(m-j+1)+g[i-1][j])%p; } g[i][i]=f[i][i]; for(register int j=i-1;j>=1;j--) { g[i][j]=(g[i][j+1]+f[i][j])%p; } } printf("%d\n",g[n][1]); return 0; } -
-1
思路
f[i][j]为考虑前i个位置，[i-j+1,i]中的颜色互不相同，并且a[i-j] 与这段区间中的某一个位置颜色相同。我们枚举第 i+1个位置和[i-j+1,i]中的哪一个颜色相同或者全部不同，进行转移:
a[i+1] 与前面 [i-j+1,i] 中全部不同时可以得到第一个转移方程： f[i+1][j+1] = f[i][j] * (m - j)
a[i+1] 与前面 [i-j+1,i] 中其中一个颜色相同时可以得到第二个转移方程： f[i+1][k] += f[i][j] (k ≤ j ≤ m)
参考代码
for (int i=1;i<=n;i++) { for (int j=1;j<=min(i,m-1);j++) { (f[i][j]+=f[i-1][j-1]*(m-(j-1))%p)%=p; (f[i][j]+=sum[i-1][j])%=p; } for (int j=m-1;j>=1;j--) sum[i][j]=(sum[i][j+1]+f[i][j])%p; }
hetao1267961
LV 10
@ 2024-3-22 20:15:05
- 1