UOJ Logo

NOI.AC

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;
}

这程序好像有点Bug,我给组数据试试?

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 1236kb

input:

4 4
1111
1011
1100
1100

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

1 1000
011001110110011101110110000011110011001001110111010001110001110100100010011010001001110111100...

output:

488

result:

ok 1 number(s): "488"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

1 1000
001110111101111001001110111111000101001110110110101100001111010001101111010100010010010001011...

output:

482

result:

ok 1 number(s): "482"

Test #4:

score: 10
Accepted
time: 74ms
memory: 2320kb

input:

1000 1000
010101000000101000010101111101010010100110110001100011110010100001010011001010110001001101...

output:

2001

result:

ok 1 number(s): "2001"

Test #5:

score: 10
Accepted
time: 84ms
memory: 2316kb

input:

1000 1000
000001101010101101101001010100001000011110100000011011010101000000000111001011010110011110...

output:

2001

result:

ok 1 number(s): "2001"

Test #6:

score: 10
Accepted
time: 65ms
memory: 2320kb

input:

1000 1000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2001

result:

ok 1 number(s): "2001"

Test #7:

score: 10
Accepted
time: 59ms
memory: 2320kb

input:

1000 1000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2001

result:

ok 1 number(s): "2001"

Test #8:

score: 10
Accepted
time: 74ms
memory: 2320kb

input:

1000 1000
100000010101010111000001011110000000001100000011110001110010101011110100000010011000011100...

output:

2001

result:

ok 1 number(s): "2001"

Test #9:

score: 10
Accepted
time: 63ms
memory: 2320kb

input:

1000 1000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2001

result:

ok 1 number(s): "2001"

Test #10:

score: 10
Accepted
time: 75ms
memory: 2320kb

input:

1000 1000
110001000111111010010100001000100011010001001101000001001001010111010101010111111110100001...

output:

2001

result:

ok 1 number(s): "2001"

Extra Test:

score: 0
Extra Test Passed