传送门:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2906
题意:给你n*m的方格,放置k个石子,每个方格最多放一个石子,要求第一行,最后一行,第一列,最后一列都有石子,问放置着k个石子有多少种方法。
题解:利用容斥原理,设全集为S,第一行没石子A,最后一行没石子B,第一列没石子C,最后一列没石子D,
那么答案为在S中但不在ABCD任何一个中。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=501;
const int mod=1000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
int C[N][N];
int main()
{
mset(C,0);
forb(i,0,N)
{
C[i][0]=C[i][i]=1; //边界条件
forb(j,1,i)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int T,ca=0;
si1(T);
while(T--)
{
int n,m,k;
si1(n);si2(m,k);
int sum=0;
forb(i,0,16)
{
int b=0,r=n,c=m; //r/c表示可以放置的行和列,b统计集合
if(i&1){r--;b++;} //第一行没有石头,行-1
if(i&2){r--;b++;}
if(i&4){c--;b++;}
if(i&8){c--;b++;}
if(b&1) sum=(sum-C[r*c][k]+mod)%mod; //减去奇数个
else sum=(sum+C[r*c][k])%mod; //加上偶数个
}
printf("Case %d: %d\n",++ca,sum);
}
return 0;
}
分享到:
相关推荐
Python项目开发实战:影视作品分析小程序,案例教程编程实例课程详解.pdf
hive外部表使用语句
ROS
SVM(支持向量机)案例&项目源码
该资源为scikit_learn-1.4.2-cp310-cp310-macosx_10_9_x86_64.whl,欢迎下载使用哦!
场景化落地应用推进制造企业数字化转型.pptx
该程序为labview2018版,使用ni-daqmax采集卡,pd控制程序,传感器为激光位移传感器
基于BIM智能建造实施方案[44页PPT]
电子科技大学数学实验3:数值计算实验
云实训平台QCOW2的Rocky9镜像资源
2024java面试题 通过对基础知识、面向对象编程、高级主题、分布式系统、微服务架构、安全性和实践问题的深入解析,帮助你在Java面试中脱颖而出,成功拿到理想的Offer。
算法
CONTENTS CHAPTER 1 MCS 51 Family of Microcontrollers Architectural Overview 1-1 CHAPTER 2 MCS 51 Programmer's Guide and Instruction Set 2-1 CHAPTER 3 8051,8052 and 80C51 Hardware Description 3-1 CHAPTER 4 8XC52154/58 Hardware Description 4-1 CHAPTERS 8XC51 FX Hardware Description 5-1 CHAPTER 6 87C51GB Hardware Description 6-1 CHAPTER 7 83C152 Hardware Description 7-1
电子科技大学计算机组成原理实验课1——实验2:中小规模组合逻辑设计
行李包安检门设计.doc
MongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMongoDB的相关案例.txtMong
基础复习总结题
SOT23;N—Channel沟道,30V;6.5A;RDS(ON)=30mΩ@VGS=10V,VGS=20V;Vth=1.2~2.2V;
NJUloadHRIR.m