#include <stdio.h> #include <algorithm> typedef long long ll; const int mod = 1e9+9; const int maxn = 1300; int c[maxn]; ll dp[maxn][maxn];///变化i次颜色为j int main()
{ int n,L;  scanf("%d%d",&n,&L);  dp[0][0]=1;  for(int i=n;i>=1;i--){ for(int j=L;j>=0;j--){
            dp[j][c[i]]=dp[j][c[i]]*(n-i+1)%mod;  for(int k=0;k<=n;k++){ if(c[i]!=k){
                    dp[j+1][c[i]]+=dp[j][k];  dp[j][k]=dp[j][k]*(n-i)%mod;  }
            }
            dp[j+1][c[i]]%=mod;  }
    } ll sum=0;  for(int i=0;i<=n;i++)
        sum+=dp[L][i];  printf("%d\n",(int)(sum%mod));  return 0; }

第五题我是这样做的，思路是dp，倒着从后往前做，dp[j][k]代表颜色已经变换了J次且最后颜色为k，时间复杂度为O(n^2*L)，看代码感觉应该还能优化，不过题目数据好像比较水，这样就过了