【USACO】USACO 2020 US Open Contest_usaco 2020 usaco us open contest-程序员宅基地

技术标签: 【OJ】USACO  

Problem A. Sprinklers 2: Return of the Alfalfa

若干包含右上或是左下角的矩形的并是一条单调向右、或向下的轮廓线。

考虑枚举最终两种作物的分界线,则不难发现,分界线的拐角处必须放置指定装置,其余位置可以不放置装置,也可以放置其中一种装置。因此,可以认为,轮廓线每拐一次弯,该轮廓线的贡献变为 1 2 \frac{1}{2} 21 ,从而进行动态规划计算答案。

时间复杂度 O ( N 2 ) O(N^2) O(N2)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int P = 1e9 + 7;
const int inv = (P + 1) / 2;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
char s[MAXN][MAXN];
int n, dp[MAXN][MAXN][2];
int main() {
	freopen("sprinklers2.in", "r", stdin);
	freopen("sprinklers2.out", "w", stdout);
	read(n); int cnt = 0;
	for (int i = 1; i <= n; i++) {
		scanf("\n%s", s[i] + 1);
		for (int j = 1; j <= n; j++)
			cnt += s[i][j] == '.';
	}
	dp[1][0][0] = dp[0][1][1] = 1;
	for (int i = 0; i <= n; i++)
	for (int j = 0; j <= n; j++) {
		if (dp[i][j][0]) {
			int tmp = dp[i][j][0];
			if (i < n) update(dp[i + 1][j][0], tmp);
			if (j < n && s[i][j + 1] == '.') update(dp[i][j + 1][1], 1ll * tmp * inv % P);
		}
		if (dp[i][j][1]) {
			int tmp = dp[i][j][1];
			if (j < n) update(dp[i][j + 1][1], tmp);
			if (i < n && s[i + 1][j] == '.') update(dp[i + 1][j][0], 1ll * tmp * inv % P);
		}
	}
	cout << 1ll * power(2, cnt) * (dp[n][n][0] + dp[n][n][1]) % P << endl;
	return 0;
}

Problem B. Exercise

考虑枚举质数 p p p ,指数 q q q ,记 f ( x ) f(x) f(x) 表示存在一个环长是 x x x 的倍数的置换个数。
则可以认为, p q p^q pq 对答案的贡献为
× p f ( p q ) \times p^{f(p^q)} ×pf(pq)

考虑在模 φ ( M ) = M − 1 \varphi(M)=M-1 φ(M)=M1 意义下计算 f ( x ) f(x) f(x)

显然有动态规划解法,单次计算时间复杂度 O ( N 2 ) O(N^2) O(N2) ,总时间复杂度 O ( N 3 ) O(N^3) O(N3)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
bool key[MAXN];
int P, fac[MAXN], binom[MAXN][MAXN];
int tot, prime[MAXN], f[MAXN];
void sieve(int n) {
	fac[0] = binom[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		binom[i][0] = 1;
		fac[i] = 1ll * fac[i - 1] * i % P;
		for (int j = 1; j <= i; j++)
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
	}
	for (int i = 2; i <= n; i++) {
		if (f[i] == 0) {
			prime[++tot] = f[i] = i;
			key[i] = true;
		} else key[i] = key[i / f[i]] && (f[i / f[i]] == f[i]);
		for (int j = 1; j <= tot && prime[j] <= f[i]; j++) {
			int tmp = prime[j] * i;
			if (tmp > n) break;
			f[tmp] = prime[j];
		}
	}
}
int n, dp[MAXN][2];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % (P + 1);
	else return 1ll * tmp * tmp % (P + 1) * x % (P + 1);
}
int calc(int x) {
	memset(dp, 0, sizeof(dp)), dp[n][0] = 1;
	for (int i = n; i >= 1; i--)
	for (int j = 1; j <= i; j++) {
		int coef = 1ll * binom[i - 1][j - 1] * fac[j - 1] % P;
		if (j % x == 0) {
			update(dp[i - j][1], 1ll * dp[i][0] * coef % P);
			update(dp[i - j][1], 1ll * dp[i][1] * coef % P);
		} else {
			update(dp[i - j][0], 1ll * dp[i][0] * coef % P);
			update(dp[i - j][1], 1ll * dp[i][1] * coef % P);
		}
	}
	cout << dp[0][1] << endl;
	return dp[0][1];
}
int main() {
	freopen("exercise.in", "r", stdin);
	freopen("force.out", "w", stdout);
	read(n), read(P), P--;
	sieve(n); int ans = 1;
	for (int i = 1; i <= n; i++)
		if (key[i]) ans = 1ll * ans * power(f[i], calc(i)) % (P + 1);
	cout << ans << endl;
	return 0;
}

观察上述动态规划的转移形式及其转移系数,可以将其优化至单次 O ( N ) O(N) O(N)

时间复杂度 O (

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39972971/article/details/105344133

智能推荐

ADB投屏_Android跨平台投屏软件(无需root)--scrcpy-程序员宅基地

文章浏览阅读1.8k次。之前一直使用 Chrome 的一个插件「Vysor」进行 Android 手机的投屏,但是有码率限制,高码率需要付费,最近发现一个更好的继任者「scrcpy」,就来推荐一下。本文将以 Mac 为例进行配置和使用 scrcpy,其他系统请参考官方文档,要求有一定的技术动手能力,觉得过于复杂的用户推荐使用「Apower Mirror」(使用简单,支持 Android 和 iOS)。项目介绍做过 And..._adb 投屏

【Python学习】 - sklearn学习 - 数据集分割方法 - 随机划分与K折交叉划分与StratifiedKFold与StratifiedShuffleSplit_from sklearn.model_selection import kfold-程序员宅基地

文章浏览阅读1w次,点赞9次,收藏49次。一、随机划分import numpy as npfrom sklearn import datasetsiris = datasets.load_iris()X = iris.datay = iris.target# 1)归一化前,将原始数据分割from sklearn.model_selection import train_test_splitX_train,X_tes..._from sklearn.model_selection import kfold

Mybatis一对一、一对多、多对多查询。+MYSQL-程序员宅基地

文章浏览阅读9.8k次,点赞17次,收藏81次。场景:使用三张数据表:student学生表、teacher教师表、position职位表一个学生可以有多为老师、一位老师可以有多个学生、但是一个老师只能有一个职位:教授、副教授、讲师;但是一个职位可以有多个老师:例如教授可以多人这里则产生了:一对一关系,从老师角度:老师对职位一对一一对多关系,从职位角度:职位对老师一对多多对多关系:查找被教授教导的所有学生(首先职位对..._"

自动化运维-centos 8 kickstart系统批量部署_centos8 ks-程序员宅基地

文章浏览阅读2.8k次。自动化运维-centos 8 kickstart系统批量部署了解kickstartwhat’s kickstartkickstart 是使用一个标准的站点为一些机器安装统一配置的linux 操作系统。kickstart的配置文件的获得方式:手动写入使用GUI system-config-kickstart 工具使用标准的Red Hat安装程序Anacondaanaconda-ks...._centos8 ks

ImmutableMultiDict转成dic类型(Python)-程序员宅基地

文章浏览阅读1.8w次。Flask中常见的数据类型处理问题项目常见的从前端通过Ajax返回的数据,是ImmutableMultiDict类型的,我们要处理成dic类型然后存入后台数据库。各种百度搜索,都是骗子,不如自己捣鼓。前端Ajax取数据View.py里面的处理方法a = request.values #把Ajax中的数据取出来 print(a) #输出一下,看是什么类型,Imm..._immutable

(1)Hadoop 的第一个程序 WordCount 理解_为啥第一个写word count-程序员宅基地

文章浏览阅读88次。Hadoop 的第一个程序 WordCount 理解map and Reduce 相关概念Mapmap 负责将自己区块数据, 做简单拆分, 成一个map, 这个map 是不去重的, 会在map 后面最加值, 让数据分组比如两个 机器的两个mapmachine1:# 以下数据是machine1 hdfs 区块的数据hello hello hello// 这是machine 1 的 context[ {"hello" : 1}, {"hello" : 1}, {"hello_为啥第一个写word count

随便推点

MyBatis3 DynamicSql风格语法使用指南_selectstatementprovider-程序员宅基地

文章浏览阅读1.8w次。MyBatis3-DynamicSql风格语法使用指南转载请注明出处:https://www.jjput.com/archives/dynamicsql主要演示DynamicSql风格代码如何使用,基本能应对大部分使用场景。DynamicSql基本介绍点我查看。本文主要沿着增、删、改、查的思路进行介绍,尽量涵盖日常使用所需。我这里还是要推荐一下大家看官方文档,尽量有问题先找官方文档教程,除非写的跟屎一样,但大概率不会。本次使用的是mybatis-dynamic-sql1.2.1版本<!--_selectstatementprovider

Java8特性总结(二)Lambda表达式,函数式接口,方法引用_返回值是function<integer,string>的方法-程序员宅基地

文章浏览阅读3.4k次。Lambda表达式,函数式接口,方法引用_返回值是function的方法

LRN层的实现-程序员宅基地

文章浏览阅读1.8w次。版权声明:本文为卜居原创文章,未经博主允许不得转载。卜居博客地址:http://blog.csdn.net/kkk584520LRN全称为Local Response Normalization,即局部响应归一化层,具体实现在CAFFE_ROOT/src/caffe/layers/lrn_layer.cpp和同一目录下lrn_layer.cu中。该层需要参数有:norm_lrn层

win10安装.NET 3.5报错 错误代码0X80070005 的解决方案_.net3.5错误代码0x80070005-程序员宅基地

文章浏览阅读1.2k次。然后再使用dotnetfx35.exe安装,最好以管理员方式运行。使用这个工具打开Windows更新。_.net3.5错误代码0x80070005

Image Style Transfer Using Convolutional Neural Network_image style transfer using convolution neural netw-程序员宅基地

文章浏览阅读560次。转载自:http://blog.csdn.net/gavin__zhou/article/details/53144148今天这篇是关于neual art的,也就是style transfer算法; 文章来源: A Neural Algorithm of Artistic Style, CVPR2015 Image Style Transfer Using Convolut_image style transfer using convolution neural network

基于AO/AE获取要素信息_ao怎么获取选中的group-程序员宅基地

文章浏览阅读1.5k次。基于AO/AE获取要素信息1、基于AE获取要素简单信息 Private Sub AxMapControl1_OnMouseDown(ByVal sender As Object, ByVal e As ESRI.ArcGIS.MapControl.IMapControlEvents2_OnMouseDownEvent) Handles AxMapControl1.OnMouseDown_ao怎么获取选中的group

推荐文章

热门文章

相关标签