hdu 3010 N Knight 组合数学

2024-03-21 15:18
文章标签 组合 数学 hdu knight 3010

本文主要是介绍hdu 3010 N Knight 组合数学,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


网上还没有这个题的题解,就来写一个。排在第一,开心~~


首先,这个对角线无论是主对角还是副对角,结果都是一样的,所以把题目要求的副对角改成主对角。

然后枚举对角线上摆放棋子的个数 0 <= i <= m, 这个取的方案数显然为 C(n,i).

剩下n-i个棋子的摆放都不能在这条对角线上,把每个行标号看成球,列标号看成盒子。放对角线上就相当于,把球放进自己对应的盒子。

而现在要求不在对角线,相当于把n-i个球放入自己不对应的n-i个箱子。这个问题的方案数显然是可以预处理的。 假设这个方案数是cp[n-i]

则答案就是 sigma(C(n,i)*cp[n-i]) 0 <= i <= m


然后就是求cp 的问题。 这其实就是一个错排问题。有递推公式 cp[i] = (i-1)*(cp[i-1] + cp[i-2]) 

证明见百度百科:http://baike.baidu.com/link?url=FNwD0IgZ9psNpdtw8sLz-exb9RjDLu9iqQCEfabA_gOzOVwuIQR0kdTs2o7kHxXo0GMuSVJdWj1uh3yuq9XSU_


(第一的代码藏起来了,这里给一个最初写的代码)

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
#define ls o<<1
#define rs o<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(y))
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int INF = 0x3f3f3f3f ;
const double pi = acos(-1.0);
const int MAXN = 100010;
const LL M = 20090818;LL C[1010][1010],cp[1010];
void init()
{for(int i = 0; i <= 1000; ++i) C[i][0] = C[i][i] = 1;for(int i = 2; i <= 1000; ++i)for(int j = 1; j < i; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1])%M;cp[0] = cp[2] = 1;for(int i = 3; i <= 1000; ++i) cp[i] = (cp[i-1]+cp[i-2])%M*(i-1)%M;
}
int n,m;
void solve()
{LL ans = 0;for(int i = 0; i <= m; ++i)ans = (ans + C[n][i]*cp[n-i])%M;printf("%lld\n",ans);
}
int main()
{init();while(~scanf("%d%d",&n,&m))solve();return 0;
}



这篇关于hdu 3010 N Knight 组合数学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/833019

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col