QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639940#7789. Outro: True Love WaitsD06WA 1ms4648kbC++142.0kb2024-10-14 00:15:282024-10-14 00:15:28

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 00:15:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4648kb
  • [2024-10-14 00:15:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
string s,t;
bitset<1000000>m,tmp;
int step(bitset<1000000>x)
{
	int id=x._Find_first();
	return id/2+1;
}
long long power(int n,int p)
{
	if(p==0)
	{
		return 1;
	}
	long long tmp=power(n,p/2);
	if(p%2==1)
	{
		return tmp*tmp%mod*n%mod;
	}
	return tmp*tmp%mod;
}
int calc(int k)
{
	return (power(4,k)-1)*power(3,1000000005)%mod;
}
void shuchu(bitset<1000000>x)
{
	bitset<10>w=x.to_ulong();
	cout<<w<<endl;
}
int ask(int len,int k)
{
//	shuchu(m);
//	cout<<len<<" "<<k<<endl;
	if(len<m._Find_first()+1)
	{
		return 1; 
	}
	if(!m[len-1])
	{
		return ask(len-1,k);
	}
	if(len==m._Find_first()+1&&step(m)==k)
	{
		return (calc(len/2+1)*power(2,len%2)-(len%2==0))%mod;
	}
	else if(len==m._Find_first()+1)
	{
		if(k==1)
		{
			return (calc((len-1)/2+1)*power(2,(len-1)%2)-((len-1)%2==0))%mod*power(2,1000000005)%mod*3%mod+1;
		}
		tmp=m;
	//	cout<<len-2*(step(m)-k+1)-(len%2==0)<<" "<<step(m)<<" "<<len<<" "<<k<<endl;
		tmp.set(len-2*(step(m)-k+1)-(len%2==0),1);
		m=tmp;
		return ask(len,k-1)+1;
	}
	else
	{
		if(len%2==0)
		{
			if(m[len-1-1])
			{
				tmp.reset();
				tmp.set(len-1-1,1);
				m=m^tmp;
				return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
			}
			else
			{
		//		cout<<calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod<<endl;
				return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod)%mod;
			}
		}
	//	cout<<calc((len-1)/2+1)*power(2,(len-1)%2)<<endl;
		return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int k;
		cin>>s>>t>>k;
		m=bitset<1000000>(s)^bitset<1000000>(t); 
		if(m.none())
		{
			cout<<calc(k)-1<<"\n";
		}
		else if(k>step(m))
		{
			cout<<-1<<"\n";
		}
		else
		{
			cout<<ask(max(s.size(),t.size()),k)-1<<"\n";
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4416kb

input:

4
1 10 1
1 10 2
100 0 2
11 11 3

output:

2
-1
9
20

result:

ok 4 number(s): "2 -1 9 20"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4340kb

input:

1
0 0 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 4648kb

input:

100
110111 11111 1
10110 101101 1
11010 111111 1
100110 1 1
10010 11010 1
1100 10111 1
100100 111110 1
101110 101100 1
1011 10110 1
110100 1110 1
11010 11000 1
11110 1000 1
111000 11101 1
110 1001 1
101010 11000 1
10 111110 1
110001 101000 1
1010 1000 1
10101 11 1
111011 11010 1
110001 100000 1
1100...

output:

78
59
69
70
15
38
39
3
32
60
3
29
69
12
45
52
37
3
29
64
22
39
54
69
65
27
33
76
34
18
57
13
81
15
23
70
69
36
18
23
29
42
69
54
6
0
63
3
29
15
10
16
80
24
37
59
71
13
23
31
30
34
23
48
30
48
7
44
42
3
37
75
59
29
55
39
29
28
29
70
55
16
54
48
24
18
79
60
8
27
64
58
32
6
8
37
2
69
42
44

result:

wrong answer 61st numbers differ - expected: '21', found: '30'