标签：道路   不同的   cout   fine   完成   解法   its   mes   复杂   

Description

给定一个 \(0/1\) 二进制串 \(s(|s|\le 50)\)，和两个整数 \(n,k(n\le 7,k\le 10^5)\)

从不大于将 \(s\) 循环 \(k\) 次后得到的二进制串的数中选不同的 \(n\) 个，异或和为 \(0\) 的方案

Solution

自己口胡的错误解法

题目本质上是要使所有的位置上面满足有偶数个数字相同

同时还要满足所选的 \(n\) 个数得互不相同

正难则反

每个位置上面的方案就是 \(\sum\limits_{i\in \{Even\}}^n\binom n i\)

搞个快速幂，这题就完成了 \(5\%\)

后面是两个瓶颈：

\(1.\) 满足大小关系

满足大小关系的要求就是如果两个数的前几位都一致，那么要在对方是 \(0\) 的位置上面不能是 \(1\)

所以就是考虑每个数对于答案的贡献（被包含在了多少的方案里面）

这一行后面的数字会废掉

\(2.\) 去重

这里上个容斥，把 \(n-1\) 的方案求出来，然后是 \(n-2\) 的 \(\cdots\)

（所以大概数组要开成 \(f_{7,5\times10^6}\) ）

正解

好像思路还是有点偏呢，水平还是不行，缺那种 \(dp\) 着定义状态的意识

（暂令 \(R>x_1>x_2>\cdots>x_n\)）

用 \(f_{i,st}\) 表示已经从高到低考虑了 \(i\) 位，\(st\) 表示对于当前的位置 \(i\)， \(x_i\) 和 \(x_{i-1}\) 的相等关系，如果相等就是 \(1\) ，反之则反之

然后转移的时候直接枚举这一次 \(n\) 个数当前位要填的 \(0/1\)（这里可以状压）

如果满足原来两项相同但是现在后面的比前面的大，那么就不转移了

更新下来状态直接更新答案

这样复杂度显然是不行的，而且显然忽略了题目中对 \(R\) 重复性的描述

所以发现没，又要矩阵快速幂啦

显然对于每个循环的转移方式都是一致的（因为字符串是一样的）

所以口胡就没了

然后进入了长长的 \(coding\ \ time\)

Code

#include
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int mod=1e9+7,N=60,M=2=mod?x+y-mod:x+y;}
	inline int del(int x,int y){return x-y>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
		return res;
	}
	int c[M],val[10];
	inline int lowbit(int x){return x&(-x);}
	inline int calc(int x){int cnt=0; for(;x;x-=lowbit(x)) cnt++; return cnt;}
	signed main()
	{
		n=read(); k=read(); scanf("%s",s+1); len=strlen(s+1); S=(1>(num-1)&1;
						val[0]=s[i]-‘0‘;
						for(int num=1;num

做题随想

原来听说过一句话「选择 \(OI\) 是享受了独立思考的快乐」

我面对这道题，思路确实是偏了

没有往状压那个方向去想

其实那种状态前面也不是没有见过，奇怪的道路和这个不无相似之处

还是不行，感觉最近状态正在转佳呀

我还真是第一次说出「这题爱谁会，谁会吧，我不管了」这种颓废的话

以后不能这样了

思路偏了拧回来就好了不是吗

耐心，耐心，耐心

其实最后写完了发现也就那个样子，根本不是自己

状压题目关键要找到状态比较复杂的点

现在做过的一些题目中主要体现在位的奇偶性和大小关系

Luogu5772 [JSOI2016]位运算

标签：道路   不同的   cout   fine   完成   解法   its   mes   复杂   

原文地址：https://www.cnblogs.com/yspm/p/13420044.html