方案数,$dp$。

总的方案数有$n^m$种,符合要求的直接算不好算,可以算反面,即不符合要求的。

设$dp[i][j]$表示前$i$种等级填了$j$个位置,那么$dp[i][j]=sum(dp[i-1][j-k]*c[m-(j-k)][k])$。初始化$dp[0][0]=1$。

符合要求的方案数为$n^m-dp[n][m]$。数字会爆$long$ $long$,上$java$。

import java.math.BigInteger;
import java.util.Scanner; public class Main { public static BigInteger GCD(BigInteger a,BigInteger b)
{
if(b.equals(BigInteger.ZERO)) return a;
return GCD(b,a.mod(b));
} public static void main(String [] args)
{
Scanner cin = new Scanner(System.in);
int M,N,L; BigInteger c[][] = new BigInteger[105][105];
BigInteger dp[][] = new BigInteger[105][105]; for(int i=0;i<=100;i++) c[i][0] = c[i][i] = BigInteger.ONE;
for(int i=1;i<=100;i++)
{
for(int j=1;j<i;j++)
{
c[i][j]= c[i-1][j-1].add(c[i-1][j]);
}
for(int j=i+1;j<=100;j++) c[i][j] = BigInteger.ZERO;
} while(cin.hasNext())
{
M=cin.nextInt();
N=cin.nextInt();
L=cin.nextInt(); if(L>M) System.out.println("mukyu~");
else
{ BigInteger n = BigInteger.valueOf(N); BigInteger fm = n.pow(M);
BigInteger fz = new BigInteger("0"); for(int i=0;i<=N;i++)
{
for(int j=0;j<=M;j++)
{
dp[i][j] = BigInteger.ZERO;
}
} dp[0][0] = BigInteger.ONE; for(int i=1;i<=N;i++)
{
for(int j=0;j<=M;j++)
{
for(int k=0;k<=L-1;k++)
{
if(j-k<0) continue;
if(M-(j-k)<0) continue; dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(c[M-(j-k)][k]));
}
}
} fz=dp[N][M]; fz = fm.subtract(fz);
BigInteger gcd = GCD(fz,fm);
fz=fz.divide(gcd); fm=fm.divide(gcd);
System.out.println(fz+"/"+fm); }
}
}
}

最新文章

  1. 3.bootstrap练习笔记-媒体内容
  2. MVC 中的 ispostback
  3. Mysql源码分析--csv存储引擎
  4. 有了iscsi存储怎么让主机识别以及使用创建lvm
  5. minicom 使用教程
  6. 《openstack 和hadoop的区别是什么?》
  7. SGU 280.Trade centers(贪心)
  8. poj3415
  9. cocos2dx 资源合并.
  10. gdb 调试coredump文件过程
  11. 判断一个指定的Service是否存在的方法
  12. java内部类demo
  13. C#之winform实现文件拖拽功能
  14. javascript语法之String对象
  15. quartz之CronExpression表达式
  16. android中的LaunchMode详解----四种加载模式
  17. 关于sizeof与#pragma pack 以及网络上关于字节对齐的一点感想
  18. upcast 做了什么操作
  19. Prometheus 监控 Nginx 流量 (三)
  20. Delphi访问网页中的下拉菜单

热门文章

  1. P1650 田忌赛马
  2. VB托盘图标不响应WM_MOUSEMOVE的原因及解决方法
  3. C&amp;C++——段错误(Segmentation fault)
  4. Java的外部类为什么不能使用private、protected进行修饰
  5. SpringMVC学习 -- 使用 @RequestMapping 映射请求
  6. svn“Previous operation has not finished; run &#39;cleanup&#39; if it was interrupted“ 或者不能cleanup,或者提示空目录 报错的解决方法
  7. 修复ios上第三方输入法弹出时输入键盘盖住网页没有进行相应滚动从而盖住表单输入框的问题
  8. linux编译动态库 fPIC作用
  9. 【SPOJ-QTREE】树链剖分
  10. laravel 获得各个根文件夹路径的方法及路由的一些使用