UOJ Logo

NOI.AC

ID提交记录ID题目HackerOwner结果提交时间测评时间
#149#196634#3433. Crisscrosstkswlsxv_hyyFailed.2024-03-29 13:09:422024-03-29 13:09:43

详细

Extra Test:

Invalid Input

input:

328964732984 8543267426349

output:


result:

FAIL Expected int32, but "328964732984" found (stdin)

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196634#3433. Crisscrossxv_hyy100495ms2320kbC++111.7kb2023-10-29 09:31:242023-11-14 17:28:57

answer

#include<bits/stdc++.h>
using namespace std;
#define ls(p) (p<<1)
#define rs(p) (ls(p)^1)
#define int long long
typedef pair<int,int> pii;
//typedef long long ll;
const int mod=1e9+7;
const int Mod=100024729991;
const int MOD=998244853;
const double eps=1e-6;
const int INF=LONG_LONG_MAX;
const int N=1005;
int a[N],b[N],n,m,cnt; 
char s[N][N];
set<int> Set;
inline int read();
inline void Hash(){
	int base=19,val=0;
	for(int i=1;i<=n;++i){
		val=(val+a[i]*base%mod)%mod;
		base=base*base%mod;
	}
	Set.insert(val);
	cnt++;
//	cout<<"\n";
//	if(Set.size()==x){
//		for(int i=1;i<=n;++i){
//			cout<<a[i]<<"\n";
//		}
//	}	
//	printf("%lld\n",Set.size());
}
inline int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod,b>>=1;
	}
	return ans;
}
inline void solve(){
//	freopen("test.in","r",stdin);
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		scanf("%s",s[i]);
		for(int j=0;j<m;++j){
			if(s[i][j]=='0')continue;
			a[i]=((a[i]+qpow(2,m-j-1))%mod+mod)%mod;
		}
		b[i]=a[i];
	}
//	for(int i=1;i<=n;++i){
//			cout<<a[i]<<"\n";
//		}
	for(int i=0;i<=n;++i){
		int x=a[i];
		a[i]=(qpow(2,m)-1+mod)%mod;
		Hash();
		a[i]=x;
	}
	for(int j=1;j<=m;++j){
//	int j=1;
	//	cout<<"\n";
		for(int i=1;i<=n;++i){
			if(s[i][j-1]!='0')continue; 
			a[i]=((a[i]+qpow(2,m-j))%mod+mod)%mod;
	//		cout<<qpow(2,m-j)<<"\n";
		} 	
		Hash();
		for(int i=1;i<=n;++i){
			a[i]=b[i];
		}
	}
	printf("%lld\n",Set.size());
}
signed main(){
	int T=1;
//	int T=read();
	while(T--)solve();
	return 0;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}