题目大意:略。(注意King只能走周围8格)
解题思路:将水平和竖直分开考虑,l[i]表示竖直上走i步不出界的种数,r[i]表示水平上走i步不出界的种数,然后枚举水平竖直走的步数(相加为k),并且要乘以组合数。因为确定步数了但是还要考虑先后的关系。
处理步数的时候,开一个二维数组dp[i][j],表示i步,位置在j的种数,j为偏移,j-k为负数表示在起始点左/上的|j−k|位置,j-k为正数表示在起点右/下的|j−k|的位置上。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1010;
const ll MOD = 9999991;
int n, m, k, x, y;
ll l[N], r[N], g[N][N*2], c[N][N];
void cat (ll* a, int x, int t) {
memset(g, 0, sizeof(g));
g[0][k] = 1;
int up = k-(x-1);
int down = k+(t-x);
for (int i = 1; i <= k; i++) {
for (int j = up; j <= down; j++) {
if (g[i-1][j]) {
if (j != up) {
g[i][j-1] = (g[i][j-1] + g[i-1][j]) % MOD;
if (j != up+1)
g[i][j-2] = (g[i][j-2] + g[i-1][j]) % MOD;
}
if (j != down) {
g[i][j+1] = (g[i][j+1] + g[i-1][j]) % MOD;
if (j != down-1)
g[i][j+2] = (g[i][j+2] + g[i-1][j]) % MOD;
}
}
a[i-1] = (a[i-1] + g[i-1][j]) % MOD;
}
}
for (int i = up; i <= down; i++)
a[k] = (a[k] + g[k][i]) % MOD;
}
void input () {
for (int i = 0; i < N; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 0; j < i; j++)
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
}
void init () {
cin >> n >> m >> k >> x >> y;
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
cat(l, x, n);
cat(r, y, m);
}
ll solve () {
ll ans = 0;
for (int i = 0; i <= k; i++)
ans = (ans + (l[i] * r[k-i]) % MOD * c[k][i])%MOD;
return ans;
}
int main () {
input();
int cas;
cin >> cas;
for (int i = 1; i <= cas; i++) {
init();
cout << "Case #" << i << ":" << endl;
cout << solve() << endl;
}
return 0;
}
分享到:
相关推荐
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU的一题........HDU DP动态规
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告