QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463793#7302. Walk of Length 6LynkcatAC ✓397ms4008kbC++206.9kb2024-07-05 14:28:272024-07-05 14:28:27

Judging History

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

  • [2024-07-05 14:28:27]
  • 评测
  • 测评结果：AC
  • 用时：397ms
  • 内存：4008kb
查看
  • [2024-07-05 14:28:27]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
//#define N
using namespace std;
const int N=1005;
int n;
bitset<N>a[N];
int du[N];
int b[15];
void BellaKira()
{
	for (int i=1;i<=n;i++) du[i]=0;
	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			a[i][j]=c-'0';
		}
	for (int i=1;i<=n;i++) 
		for (int j=1;j<=n;j++)
			du[i]+=a[i][j];
	//(1,5) -(1,5) (2,4)
	for (int i=1;i<=n;i++)
	{
		int t=0,p=0;
		for (int j=1;j<=n;j++)
		{
			int x=(a[i]&a[j]).count();
			ans+=x*(x-1)*du[i];
		}
	}
    // cerr<<"g "<<ans<<endl;
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             if (b[1]==b[5]) 
    //             {
    //                 ans--;
    //             }
    //             if (b[1]==b[5]&&b[2]==b[4]) ans++;
    //         }
    // cerr<<"f "<<ans<<endl;

	//(1,3)+(3,5)+(2,4) -(1,3)(2,4) -(2,4)(3,5)
	for (int i=1;i<=n;i++)
	{
		int t=0,p=0;
		for (int j=1;j<=n;j++)
		{
			int tp=(a[i]&a[j]).count();
			ans=(ans+du[j]*tp*tp*3);
			ans=(ans-tp*tp*2);
		}
	}
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             if (b[1]==b[3]) ans--;
    //             if (b[2]==b[4]) ans--;
    //             if (b[3]==b[5]) ans--;
    //             if (b[1]==b[3]&&b[2]==b[4]) ans++;
    //             if (b[3]==b[5]&&b[2]==b[4]) ans++;
    //         }
    // cerr<<"f "<<ans<<endl;

	//-2*(1,3)(1,5)(3,5)
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				ans-=2*du[j]*du[j];
			}
	}
    // cerr<<"g "<<ans<<endl;
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             if (b[1]==b[3]&&b[1]==b[5]) ans+=2;
    //         }
    // cerr<<"f "<<ans<<endl;
	// cout<<"?"<<ans<<endl;
	//(1,4)+(2,5)
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				int tp=(a[i]&a[j]).count();
				t+=tp;
			}
		ans+=t*t*2;
	}
    // cerr<<"g "<<ans<<endl;
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             if (b[1]==b[4]) ans--;
    //             if (b[2]==b[5]) ans--;
    //         }
    // cerr<<"f "<<ans<<endl;
    // cerr<<"g "<<ans<<endl;
	// cout<<"?"<<ans<<endl;
	//-(1,4)(3,5)*3
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				int tp=(a[i]&a[j]).count();
				ans-=tp*tp*3;
			}
	}
    // cerr<<"g "<<ans<<endl;
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             if (b[1]==b[4]&&b[3]==b[5]) ans++;
    //             if (b[1]==b[4]&&b[2]==b[5]) ans++;
    //             if (b[1]==b[3]&&b[2]==b[5]) ans++;
    //         }
    // cerr<<"f "<<ans<<endl;
	// cout<<"?"<<ans<<endl;
	//(1,3)(3,5)(1,5)(2,4) *2
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
                ans+=du[i]*2;
			}
	}
    // cout<<"!!!"<<ans<<endl;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j)
            {
                int x=(a[i]&a[j]).count();
                // cout<<i<<","<<j<<" "<<x<<endl;
                ans+=x*(x-1)*(du[j]-2-a[i][j])*2;
            }

    // cout<<"!!!"<<ans<<endl;
    // //(3,6)
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				int tp=(a[i]&a[j]).count();
				t+=tp;
			}
		ans+=t*t;
	}
    //-(3,6)(1,5) -(3,6)(2,4) -(3,6)(1,4) -(3,6)(2,5)
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				int tp=(a[i]&a[j]).count();
				ans-=tp*tp*4;
			}
	}
    //(3,6)(1,5)(2,4) (3,6)(1,4)(2,5)
	for (int i=1;i<=n;i++)
	{
		int t=0;
		for (int j=1;j<=n;j++)
			if (a[i][j])
			{
				int tp=(a[i]&a[j]).count();
				ans+=tp*2;
			}
	}
    
	cout<<ans<<'\n';
    // for (b[1]=1;b[1]<=n;b[1]++)
    //     for (b[2]=1;b[2]<=n;b[2]++)
    //         if (a[b[1]][b[2]])
    //     for (b[3]=1;b[3]<=n;b[3]++)
    //         if (a[b[2]][b[3]])
    //     for (b[4]=1;b[4]<=n;b[4]++)
    //         if (a[b[3]][b[4]])
    //     for (b[5]=1;b[5]<=n;b[5]++)
    //         if (a[b[4]][b[5]])
    //     for (b[6]=1;b[6]<=n;b[6]++)
    //         if (a[b[5]][b[6]])
    //         if (a[b[6]][b[1]])
    //         {
    //             for (int i=1;i<=6;i++) cout<<b[i];
    //             cout<<'\n';
    //             bool bl=0;
    //             for (int x=1;x<=5;x++)
    //                 for (int y=x+1;y<=5;y++)
    //                     if (b[x]==b[y]) cout<<"("<<x<<","<<y<<");",bl=1;
    //             cout<<endl;
    //             ans--;
    //         }
	// cout<<ans<<'\n';
	
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (cin>>n)
	{
		BellaKira();
	}
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3888kb

input:

3
011
101
110
4
0101
1010
0101
1010
6
011111
101111
110111
111011
111101
111110

output:

66
128
14910

result:

ok 3 number(s): "66 128 14910"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

1
0
2
01
10
3
011
100
100
3
011
101
110
4
0001
0001
0001
1110
4
0101
1001
0001
1110
4
0100
1001
0001
0110
4
0101
1011
0101
1110
4
0110
1001
1001
0110
4
0111
1011
1101
1110
5
01000
10111
01000
01000
01000
5
01111
10001
10000
10000
11000
5
01100
10110
11011
01100
00100
5
01111
10110
11010
11100
10000
...

output:

0
2
16
66
54
116
36
298
128
732
128
202
408
878
80
172
794
1372
56
372
668
190
2370
142
300
300
100
650
1216
432
4100
250
336
566
1072
988
1602
850
2648
446
1434
4438
160
264
524
1030
130
802
258
362
1380
518
1650
2372
3538
5460
488
106
234
892
1542
482
362
790
1326
2186
288
1176
1784
808
5232
7358
...

result:

ok 143 numbers

Test #3:

score: 0
Accepted
time: 8ms
memory: 3588kb

input:

20
01110111111111111111
10111111111011111111
11011111101111101111
11101110111011111111
01110111111011011011
11111011101111011110
11111101111111101111
11101110111111111111
11111111011111111111
11011011101111101111
11111111110111010111
10100111111011111111
11111111111101111110
11111111111110111111
111...

output:

11368772
12823048
16678042
17149212
18099376
18616410
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
191...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 20ms
memory: 3656kb

input:

50
01111111111101010111111110111111111111001110111111
10111111011010111101111111011111111111111111011111
11010101111111111110011110001111111111111111111111
11101111110101111110101111111111111111111101111111
11010111111101101111011111111101111111101111111110
111110111011111111111111111111111111111101...

output:

1250940348
1590514050
1984065786
2169894880
2338139630
2348971408
2399983250
2399983250
2389639440
2389639440
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250

result:

ok 20 numbers

Test #5:

score: 0
Accepted
time: 358ms
memory: 3680kb

input:

1000
0110000100111110011111111011111111111111111010111011111111110111111111110111110011101111110111111110110111111111111011111100101111000111011011101111110011111101110110111011100111111101101110101111001011011101011101111101111111111111000110011011010111111111111111111010111011011110010111011111101...

output:

1943182464425962

result:

ok 1 number(s): "1943182464425962"

Test #6:

score: 0
Accepted
time: 375ms
memory: 4008kb

input:

1000
0111101111111111110111111111110011101111111101111011110111111110111011011101111110111111111111111111111111111110111110111110111101110110111111101111111111101101111111011011111111111111011111111111111111111011111111111111111110111111111111101111111101111011111111111111111111111111111000111111111...

output:

4406302098164568

result:

ok 1 number(s): "4406302098164568"

Test #7:

score: 0
Accepted
time: 390ms
memory: 3724kb

input:

1000
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111011111111111111111...

output:

7524709536316820

result:

ok 1 number(s): "7524709536316820"

Test #8:

score: 0
Accepted
time: 393ms
memory: 3720kb

input:

1000
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

8841456311725232

result:

ok 1 number(s): "8841456311725232"

Test #9:

score: 0
Accepted
time: 394ms
memory: 3668kb

input:

1000
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

8930014130020796

result:

ok 1 number(s): "8930014130020796"

Test #10:

score: 0
Accepted
time: 397ms
memory: 3720kb

input:

1000
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

8930204741115000

result:

ok 1 number(s): "8930204741115000"

Test #11:

score: 0
Accepted
time: 168ms
memory: 3712kb

input:

1000
0000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

55816

result:

ok 1 number(s): "55816"

Test #12:

score: 0
Accepted
time: 167ms
memory: 3720kb

input:

1000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-02 23:49:43 | OpenSource Project