网站如何制作,wordpress注册美化,linux做网站服务器那个软件好,网站建设与管理 试卷Cheerleaders UVA - 11806
题目传送门
题目大意#xff1a;给你三个整数n,m,k#xff0c;代表有一个n行m列的场地#xff0c;共有k个人#xff0c;需保证在最外围的一圈的每行每列都必须要有一个人#xff0c;若这个人在对角上#xff0c;则可以当做他所在的行列都已经…Cheerleaders UVA - 11806
题目传送门
题目大意给你三个整数n,m,k代表有一个n行m列的场地共有k个人需保证在最外围的一圈的每行每列都必须要有一个人若这个人在对角上则可以当做他所在的行列都已经满足条件问共有几种排布方法。
解决方法此题若是从正面算十分复杂因此换一种思路假设场地的四边分别为A,B,C,D总的情况数为C(底数n*m)(指数k)不满足条件的情况为有一条边A,B,C,D不放人有两条边不放人AB,AC,AD,BC,BD,CD有三条边不放人ABC,ABD,ACD,BCD四条边全不放人ABCD所以满足条件的情况为总的情况数-缺一条边缺两条边-缺三条边缺四条边。
AC代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e67;
ll C[510][510];
void fun()
{C[1][1]1;C[1][0]C[2][0]C[2][2]1;C[2][1]2;for(int i3;i500;i){C[i][0]C[i][i]1;for(int j1;ji;j)C[i][j](C[i-1][j]C[i-1][j-1])%mod;}
}
int main()
{//freopen(in.txt, r, stdin);//freopen(out.txt, w, stdout);ios::sync_with_stdio(0),cin.tie(0);int T;fun();
/* int u,v; while(cinuv)coutC[u][v]endl;*/cinT;ll t1,t2,t3,t4,t5,t6,t7,t8,t9;rep(i,1,T) {ll n,m,k,a,b,c,d;cinnmk;t1n*m;t2n*(m-1);t3(n-1)*m;t4(n-2)*m;t5(n-1)*(m-1);t6n*(m-2);t7(n-2)*(m-1);t8(n-1)*(m-2);t9(n-2)*(m-2);ll allC[t1][k];a((C[t2][k]C[t3][k])*2)%mod;b(C[t4][k]C[t5][k]*4C[t6][k])%mod;c(C[t7][k]*2C[t8][k]*2)%mod;dC[t9][k];ll ansall-ab-cd;
/* coutall a b c dendl;
*/ coutCase i: ;if(k2)cout0endl;elsecout(ansmod)%modendl;}return 0;
}
