ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196634 | #3433. Crisscross | xv_hyy | 100 | 495ms | 2320kb | C++11 | 1.7kb | 2023-10-29 09:31:24 | 2023-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