题目连接:uva 11916 - Emoogle Grid
题目大意:有一问题,在M行N列的网格上涂K种颜色,其中有B个格子不用涂色,其它每个格子涂一种颜色,同一列的上下两个相邻的格子不能涂相同的颜色。给出M,N,K和B个格子的位置,求出总方案数模掉1e8+7的结果R。现在已知R,求最小的M。
解题思路:有确定不用涂色格子的区域作为不变部分,总数通过计算为tmp,外加可变部分的第一行,方案数为cnt,可变部分除第一行外,每加一行都将总数乘以(K−1)N,既有
- cnt∗PM=Rmod(1e8+7)
- PM=cnt−1∗Rmod(1e8+7)
就是大步小步算法求M。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1e8+7;
const int maxn = 505;
int N, M, K, R, B, X[maxn], Y[maxn];
set<pair<int, int> > bset;
inline ll mul_mod (ll a, ll b) {
return (ll)a * b % MOD;
}
inline ll pow_mod (ll a, ll n) {
ll ans = 1;
while (n) {
if (n&1)
ans = mul_mod(ans, a);
a = mul_mod(a, a);
n /= 2;
}
return ans;
}
void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
gcd (b, a%b, d, y, x);
y -= x * (a/b);
}
}
inline ll inv (ll a) {
ll d, x, y;
gcd(a, MOD, d, x, y);
return d == 1 ? (x+MOD)%MOD : -1;
}
void init () {
scanf("%d%d%d%d", &N, &K, &B, &R);
bset.clear();
M = 1;
for (int i = 0; i < B; i++) {
scanf("%d%d", &X[i], &Y[i]);
M = max(M, X[i]);
bset.insert(make_pair(X[i], Y[i]));
}
}
int count () {
int c = 0;
for (int i = 0; i < B; i++) {
if (X[i] != M && !bset.count(make_pair(X[i]+1, Y[i])))
c++;
}
c += N;
for (int i = 0; i < B; i++)
if (X[i] == 1)
c--;
return mul_mod(pow_mod(K, c), pow_mod(K-1, (ll)M*N-B-c));
}
int log_mod (ll a, ll b) {
ll m = (ll)sqrt(MOD+0.5), v, e = 1;
v = inv(pow_mod(a, m));
map<ll, ll> g;
g[1] = 0;
for (ll i = 1; i < m; i++) {
e = mul_mod(e, a);
if (!g.count(e))
g[e] = i;
}
for (ll i = 0; i < m; i++) {
if (g.count(b))
return i*m+g[b];
b = mul_mod(b, v);
}
return -1;
}
int doit () {
int cnt = count();
if (cnt == R)
return M;
int c = 0;
for (int i = 0; i < B; i++)
if (X[i] == M)
c++;
M++;
cnt = mul_mod(cnt, pow_mod(K, c));
cnt = mul_mod(cnt, pow_mod(K-1, N-c));
if (cnt == R)
return M;
return log_mod(pow_mod(K-1, N), mul_mod(R, inv(cnt))) + M;
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init();
printf("Case %d: %d\n", i, doit());
}
return 0;
}
分享到:
相关推荐
课程设计污水处理
PHP基于Web的subversion用户管理系统(源代码+设计说明书).zip
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
The Experiment 3 of Engineering Electromagnetics.pdf
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
JSP网络购物中心毕业设计(源代码+设计说明书).zip
卷积神经网络 卷积神经网络_基于VGGNet实现的遥感图像分类算法
node-v0.12.10.tar
转型计划gl.ppt
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
led.zip
ASP+ACCESS实验室设备管理系统(源代码+设计说明书).zip
jsp网上超市设计与实现(源代码+设计说明书).zip
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
商业分析工具:常用战略分析工具gl.ppt
行业分析模板--初学者必备gl.ppt
dephi+sqlserver2000题库与试卷生成系统.zip
基于matlab实现阵列信号处理MVDR程序,高分辨方位估计从事人员可供参考。.rar
一种全新的基于python 用于疲劳强度迟滞回线的脚本分析.rar
基于matlab实现的对数据进行傅立叶分析,从时域转换到频域,观察信号的频谱结构,从分析信号的特点.rar