传送门: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;
}
分享到:
相关推荐
为超休闲拉拉队创作的一组角色和道具。 可以与所有类型的照明和渲染管道一起使用。 包含21个独特的预制资产。 8个角色预制(人形装备) 13个预制道具 道具采用单1024x1024纹理 多材质字符 每个对象的平均多边形数约...
- **Cheerleaders**: 通过让学生拼写单词,这个游戏加强了字母与发音的关联,提高了单词拼读能力。 - **Hang Man**: 游戏中学生需要猜测单词,强化了单词拼写和词汇量。 2. **词汇游戏** - **分组游戏**: 这类...
We have athletes, and either coaches or cheerleaders! {% endif %} {% endif %} ``` 此外,为了实现类似`{% elif %}`的功能,可以通过嵌套`{% if %}`标签来实现: ```html {% if athlete_list %} <p>Here ...
微信小程序Artandw_eapp-artand
本项目是一款基于Vue和JavaScript开发的心旅途个性化推荐旅游平台设计源码,整合了513个Java文件、76个PNG图片、70个XML配置文件、62个JavaScript文件、42个Vue组件文件、28个CSS样式文件、22个HTML文件、18个YAML配置文件、16个属性文件、11个Vue模板文件,总计919个文件。平台采用现代化前端技术堆栈,旨在为用户提供个性化的旅游推荐服务。
微信小程序开发地图演示、地图导航、标记标注_echat-weapp-mpdemo
Vue和Axios文件
该项目为基于Python语言开发的HTML与任务清单关系系统,包含50个文件,其中16个为HTML文件,14个为Python源代码文件,其余包括Python编译文件、Markdown文件、图片、数据库文件、配置文件、模板文件、文本文件等,旨在为用户提供简单便捷的生活时间段安排及任务规划管理工具。
全国大学生电子设计大赛项目合集全国电赛优秀作品大学生电子竞赛历届题目
该项目是一款基于Python和pygame引擎开发的植物大战僵尸游戏,包含125个文件,涵盖93个PNG图像文件、11个Python源代码文件、10个Python字节码文件、8个GIF动画文件、1个Git忽略配置文件、1个JSON数据文件以及1个Markdown说明文件。游戏设计源码为学习游戏开发提供了丰富的实践素材。
本项目是一款以Java为核心开发的Qiniu服务端设计源码整合的RunFlow桌面端效率工具,总文件数29个,包括17个Java源文件、2个属性文件、1个Git忽略文件、1个JAR包文件、1个LICENSE文件、1个Markdown文件、1个YAML文件、1个Maven配置文件和1个命令文件。该工具旨在提升工作效率,适用于各种桌面环境下的便捷使用。
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
Golang支付-微信公众号、微信应用、微信小程序、微信企业支付、支付宝网络版、支付宝应用、支付宝企业支付_支付宝
医疗辅助诊断系统-开题
该项目为东东购物网的后台开发源码,采用JavaScript为主要编程语言,辅以CSS、Java、HTML等多种语言,共包含1300个文件。具体文件类型分布如下:458个PNG图片文件、215个JavaScript文件、160个JPG图片文件、159个GIF图片文件、107个CSS样式表文件、96个Java源代码文件、28个HTML文件、24个XML文件、12个JSON文件、8个Map文件。该系统旨在提供高效、便捷的购物后台管理功能。
content_1728052071778.apk
资源视频编辑软件win781064位系统
职业心理测试人格气质情绪控制测试18个文件
那些年,与你同分同位次的同学都去了哪里?全国各大学在辽宁2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
该项目为基于Python语言的微信小程序源码,全面整合了JavaScript和微信小程序开发技术。项目结构包含50个文件,涵盖了15个PNG图片、9个JSON配置、8个JavaScript脚本、7个wxss样式表、6个WXML模板和4个JPG图片。此外,还包括1个Markdown文档。该小程序的设计与实现展现了Python编程的强大能力,适用于微信生态下的各类应用场景。