19-11-10-Night

关于$Miemeng$，它死了。

大家有没有记得我在暑假里曾经写过一个著名模数？
const int Mod=998224353;
现在有续集了（捂脸）（改不过题.jpg）
const int Mod=988244353;

ZJ：

我对不起大家我又咕咕咕了，话说为什么我挂起的电脑……

T1Adore，看起来很熟悉……不知道是什么时候见过这个词……

于是发现不可做。打一个暴力就丢了。

T2发现暴力很好打，先码了一个，先rand了几个数据，发现答案大都是$1\ 2$

emm，本来想一边输入一边扫，但是后来弃掉了（为什么要弃啊啊啊？

T3发现很贪心，但是只会输出$n$（滑稽

（后来听说输出$\frac{n}{s}$有$50$）

Miemeng

00:00:03

00:00:04

00:00:05

啊T1为什么爆〇了？？？？

TJ:

T1

状压即可，设$f_{i,s}$为第$i$层点权奇偶性为$s$（奇为$1$，偶为$0$）时前$i$层的方案数

于是预处理取反边，并且直接转移就好了。

最后的答案就是$f_{n,0}$

复杂度$\Theta(NK 2^K)$

#include <iostream>

#include <cstring>

#include <cstdio>

//#include "debug.h"

#define N 11111

#define K 12

#define S (1<<K)+111

#define LL long long

using namespace std;

const int Mod=998244353;

int cn,pn;

LL dp[N][S];

int mp[N][K],pm[N][K];

int dat[N][K][K];

void prerun(){

	for(int i=1;i<=pn;i++){

		mp[1][1] |= dat[1][1][i]<<(i-1);

	}

	for(int i=2;i<cn-1;i++){

		for(int j=1;j<=pn;j++){

			for(int k=1;k<=pn;k++){

				mp[i][j] |= dat[i][j][k]<<(k-1);

				pm[i][k] |= dat[i][j][k]<<(j-1);

			}

		}

	}

	for(int i=1;i<=pn;i++){

		mp[cn-1][i] |= dat[cn-1][i][1];

//		cout<<mp[cn-1][i]<<" ";

	}

//	cout<<endl;

}

int main(){

#ifndef LOCAL

	freopen("adore.in" ,"r",stdin);

	freopen("adore.out","w",stdout);

#endif

	scanf("%d%d",&cn,&pn);

	for(int i=1;i<=pn;i++){

		scanf("%d",&dat[1][1][i]);

	}

	for(int i=2;i<cn-1;i++){

		for(int j=1;j<=pn;j++){

			for(int k=1;k<=pn;k++){

				scanf("%d",&dat[i][j][k]);

			}

		}

	}

	for(int i=1;i<=pn;i++){

		scanf("%d",&dat[cn-1][i][1]);

	}

	prerun();

/*	for(int i=1;i<=cn;i++){

		for(int j=1;j<=pn;j++){

			cout<<i<<" "<<j<<" "<<bin(mp[i][j],pn)<<endl;

		}

	}*/

	dp[2][mp[1][1]]=1;

	for(int i=2;i<cn-1;i++){

		for(int s=0;s<1<<pn;s++){

//			cout<<"dp["<<i<<"]["<<bin(s,pn)<<"]="<<dp[i][s]<<endl;

			int pos=0,sop=0;

			for(int j=1;j<=pn;j++){

				int k=1<<(j-1);

				if(k&s){

					pos^=mp[i][j];

					sop^=pm[i][j];

				}

			}

			dp[i+1][pos]+=dp[i][s];

			dp[i+1][pos]%=Mod;

			dp[i+1][sop]+=dp[i][s];

			dp[i+1][sop]%=Mod;

		}

	}

	for(int s=0;s<1<<pn;s++){

		int pos=0;

//		cout<<"dp["<<cn-1<<"]["<<bin(s,pn)<<"]="<<dp[cn-1][s]<<endl;

		for(int i=1;i<=pn;i++){

			int j=1<<(i-1);

			if(j&s){

				pos^=mp[cn-1][i];

//				cout<<"pos:"<<bin(pos,pn)<<"<-"<<j<<" "<<mp[cn-1][j]<<endl;

			}

		}

		dp[cn][pos]+=dp[cn-1][s];

		dp[cn][pos]%=Mod;

	}

	printf("%lld\n",dp[cn][0]);

}

T2：

考试的小剪枝暴力tong过本题。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <bitset>

#define N 6666

using namespace std;

int sn;

char str[N*100];

bitset <2*N> vals[N];

int main(){

#ifndef LOCAL

	freopen("confess.in" ,"r",stdin);

	freopen("confess.out","w",stdout);

#endif

	scanf("%d",&sn);

	for(int i=1;i<=sn+1;i++){

		int cnt=0;

		scanf("%s",str);

		int len=strlen(str);

		for(int j=0;j<len;j++){

			int dat=str[j]-33;

			for(int k=0;k<6;k++){

				vals[i]<<=1;

				cnt++;

				vals[i].set(0,dat>>k&1);

				if(cnt==2*sn)goto nxtt;

			}

		}

		nxtt:;

		for(int j=1;j<i;j++){

			if((int)(vals[i]&vals[j]).count()>=sn/2){

				cout<<i<<" "<<j<<endl;

				return 0;

			}

		}

	}

}

但是正解是随机化……

（随机化可过的题大多都可以暴力剪枝过……）

巴特西

19-11-10-Night

ZJ：

TJ:

T1

T2：

T3咕掉了，也不想粘题解。

最新文章

热门文章