首页 > 其他分享 >Math teacher's homework 题解

Math teacher's homework 题解

时间:2023-10-16 22:35:23浏览次数:38  
标签:ch int 题解 low Print include teacher homework mathrm

preface

网上的题解看不懂,看代码看懂了 :)

solution

考虑 \(\mathrm{x_i}\) 的倒数第 \(\mathrm{low_i - 1}\) 位到倒数第 \(\mathrm{1}\) 位可以乱选(选 \(\mathrm{0/1}\) 都满足 \(\mathrm{x_i \leq m_i}\)),那么就需要 \(\mathrm{x_i}\) 和 \(\mathrm{m_i}\) 的第 \(\mathrm{1}\) 位到倒数第 \(\mathrm{low_i + 1}\) 位都一样,然后 \(\mathrm{m_i}\) 倒数第 \(\mathrm{low_i}\) 位为 \(\mathrm{1}\), \(\mathrm{x_i}\) 倒数第 \(\mathrm{low_i}\) 位为 \(\mathrm{0}\)。

令 \(\mathrm{k}\) 一共有 \(\mathrm{cnt}\) 位。

\(\mathrm{dp[i][j][k]}\) 表示考虑前 \(\mathrm{i}\) 个 \(\mathrm{x}\) 的取值,\(\mathrm{low_l}\) 的最大值为 \(\mathrm{j}\) (即前 \(\mathrm{j - 1}\) 位目前是确定的,因为\(\mathrm{x_{d} (1 \leq d \leq i)}\) 的前 \(j - 1\) 位都顶到上届,第 \(j\) 位为 \(0\) (\(\mathrm{low_d = j}\)) 或者 \(1\) (\(\mathrm{low_d < j}\))),第 \(j\) 位的异或值为 \(k\)。

转移就是考虑 \(\mathrm{x_i}\) 前 \(\mathrm{d}\) 位都顶着上届,然后值得注意为了最后能等于 \(k\),倒数 \(\mathrm{j}\) 位都必须留下一位来调整使这一位等于 \(k\) 的这一位,所以最终答案要除以 \(\mathrm{2^{j}}\),当然也可以在过程中计算。

还有一种情况是选择 \(m_i\),要特殊考虑,我调了好久 :(。

//我看着,天真的我自己
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio> 
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define MP(x,y) make_pair (x, y)
#define PII pair <int, int>
#define db double
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)

template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
	x = 0; bool fl_for_x = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') {
		if (ch == '-') fl_for_x = 0;
		ch = getchar ();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar ();
	}
	if (!fl_for_x) x = -x;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
	read (x), read (args...);
}
const int Maxn_For_Print = 30;
int Tp_For_Print, St_For_Print[Maxn_For_Print + 5];
template <typename T>
void write (T x) {
	if (x == 0) {
		putchar ('0');
		return;
	}
	if (x < 0) {
		x = -x;
		putchar ('-');
	}
	while (x) {
		St_For_Print[++Tp_For_Print] = x % 10;
		x /= 10;
	}
	while (Tp_For_Print) {
		putchar (St_For_Print[Tp_For_Print--] + '0');
	}
}
template <typename T>
void print (T x, char ch) {
	write (x), putchar (ch);
}

const int Maxn = 50;
const int Maxk = 31;
const LL Mod = 1e9 + 3;

int n, k;
int a[Maxn + 5];

LL f[Maxn + 5][Maxk + 5][2];
bool vis[Maxn + 5][Maxk + 5][2];
LL dfs (int step, int low, int val) {
	//step 表示考虑 x[step] 的取值,low表示第一位到倒数第low位需要有数去修正,val表示需要修正的值(即之前的异或和)

	val = val & (~((1 << low) - 1));
	if (step == n + 1) return !val;
	if (vis[step][low][val >> low & 1]) return f[step][low][val >> low & 1];

	LL res = 0, tmp = 0;
	per (i, Maxk, 0) {
		//前 i 位顶着上届
		if (a[step] >> i & 1) {
			//第 i 位为 0,后面的乱选
			//如果 i > low,那么 [low, i] 这几位就无法自己决定为 0 / 1,就是 solution 里为了最终异或值为 k 最后用来调整的那几位不能自由选,所以要比 Min (low, i)。
			res = (res + dfs (step + 1, Max (low, i), val ^ tmp) * ((1ll << Min (low, i)) % Mod) % Mod) % Mod;
			tmp |= (1 << i);
		}
	}
	//都顶着上届,就是选择 m[i]
	res = (res + dfs (step + 1, low, val ^ tmp)) % Mod;
	f[step][low][val >> low & 1] = res, vis[step][low][val >> low & 1] = 1;
	return res;
}

signed main () {
	freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.in", "r", stdin);
	freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.out", "w", stdout);
//	freopen ("transport.in", "r", stdin);
//	freopen ("transport.out", "w", stdout);

	while (1) {
		memset (f, 0, sizeof f);
		memset (vis, 0, sizeof vis);
		read (n, k);
		if (!(n + k)) break;
		rep (i, 1, n)
			read (a[i]);
		print (dfs (1, 0, k), '\n');
	}
	return 0;
}

标签:ch,int,题解,low,Print,include,teacher,homework,mathrm
From: https://www.cnblogs.com/dsy-lh/p/17768488.html

相关文章

  • YACS 2023年9月月赛 甲组 题解
    题目链接1题目链接2题目链接3榜单终于公布了,这应该是第二长的榜单公布吧。(最长的一次是去年八月,拖到九月开始后才公布) T1是傻逼数据结构不说了吧,对于每个点枚举以他为角的$k\timesk$的四个正方形算一下点的数量,用$cdq$或者扫描线都行。看这个题目编号是$81$,看来是很......
  • 题解整理
    CF1740ACF1740BCF1740DCF1711BCF1253BCF1080BCF1237ACF1743ACF1743CCF1743BCF1370B......
  • P9744 消除序列 题解
    本题有多种解法,我这里先讲一个我的考场做法吧。切入点我们发现我们至多使用一次操作一,而剩下部分的\(0\)肯定是依靠操作二补全,操作三的作用只是用来填补操作一的空白的,所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三,后一段用操作二。思路1一开始考虑暴力\(......
  • CEIT 23练习编程题 题解
    本文部分题目提供c/c++两种解法,顺便可以让你们知道c++在面对某些题时的优势部分题目提供多种解法日期格式化C#include<stdio.h>intmain(){intm,d,y;scanf("%d-%d-%d",&m,&d,&y);printf("%04d-%02d-%02d",y,m,d);return0;}02d的含义:当有效数......
  • 【题解】「KDOI-06-S」补题
    「KDOI-06-S」A.「KDOI-06-S」消除序列赛时写了一个\(O(nq)\)的线性DP,喜提60分。注意到如果操作1被使用,则一定只会使用一次,而且在最优策略中一定是第一次使用操作1。则我们可以通过以下方式进行操作,使序列满足条件:首先执行\(a_i\)和\(\sum^{j\lei,i\inP}_{j=......
  • [COCI2015-2016#4] ENDOR 题解
    [COCI2015-2016#4]ENDOR题解首先要发现一个很重要的性质,那就是两只变色龙碰撞后回头,等效于两只变色龙继续往前走,其中向右走的颜色不变,而向左走的要改变颜色。那这样就有一种\(O(n^2)\)的做法:对于向右的变色龙,直接贡献答案;对于向左的变色龙,我们按照碰到的先后顺序枚举它前面......
  • 【题解】AtCoder-ARC167
    AtCoder-ARC167AToastsforBreakfastParty一定不会有空盘,问题转化成\(2m\)个数,其中\(2m-n\)个是\(0\),这样一定是最大值和最小值一起,次大值和次小值一起,以此类推。提交记录:Submission-AtCoderAtCoder-ARC167BProductofDivisors\(A^B=\prod_ip_i^{Bc_i}\),那么答案......
  • CF1119F Niyaz and Small Degrees 题解
    原题翻译首先\(O(n^2\logn)\)的dp是simple的,我们设\(dp_{i,0/1}\)表示以\(i\)为根,\(i\)到\(fa_i\)这条边删/不删的最小权值和。转移是一个非常trick的问题,只需要假设所有都选\(dp_{i,0}\),然后把所有儿子按照\(dp_{v,1}+w(u,v)-dp_{v,0}\)排序,选前\(d......
  • P9745 「KDOI-06-S」树上异或 题解
    P9745「KDOI-06-S」树上异或题解\(x_i=0\)这题一看就不是很可做,先考虑部分分。对于一条链的情况,我们可以枚举上一个断边的位置,然后转移。一看数据范围,估计和值域有关,所以考虑\(x_i=1\)的部分分,如果全部点权都是1,那么一种方案只有0和1两种取值,考虑这个状态设计:\(f......
  • [ARC167D] Good Permutation 题解
    题意对于一个长度为\(N\)的排列\(Q\),定义其为好的,当且仅当对于任意整数\(i\in\left[1,N\right]\),在进行若干次操作\(i\leftarrowQ_i\)后可以得到\(i=1\)。给定一个排列\(P\),定义一次操作为交换两个数。定义\(M\)为可以将\(P\)变为一个好的的排列的最小操......