Ideone.com

fork download

copy

#include<bits/stdc++.h>
#define ll long long
#define FNAME ""
#define xd "\n"
const int MAXN = (int)505;
using namespace std;
const long long MOD = (long long)1e9 + 7;
const int INF = (int)1e9;
const int LIM = (int)2e4 + 1;
#define ull unsigned long long
 
template<class X, class Y>
	bool minimize(X &a , Y b) {
		if(a > b) {
			a = b;
			return true;
		}
		return false;
	};
 
template<class X, class Y>
	bool maximize(X &a , Y b) {
		if(a < b) {
			a = b;
			return true;
		}
		return false;
	};
 
void HuuThien() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if(fopen(FNAME".inp", "r")) {
		freopen(FNAME".inp", "r", stdin);
		freopen(FNAME".out", "w", stdout);
	}
}
 
int m, n, k;
vector<bool> Prime((int)1e6 + 1, true);
vector<vector<int>> a;
 
void Sieve() {
	Prime[0] = Prime[1] = false;
	for(int i = 2; i * i <= (int)1e6 ; i++) {
		if(Prime[i]) {
			for(int j = i * i; j <= (int)1e6 ; j += i) {
				Prime[j] = false;
			}
		}
	}
}
 
void Init() {
	cin >> m >> n >> k;
	a.assign(m + 1, vector<int>(n + 1, 0));
 
	for(int i = 1; i <= m ; i++) {
		for(int j = 1; j <= n ; j++) {
			int ai;
			cin >> ai;
			a[i][j] = Prime[ai];
		}
	}
} 
 
void Solve() {
	long long ans = 0;
	for (int r1 = 1; r1 <= m; r1++) {
        for (int r2 = r1 + 1; r2 <= m; r2++) {
            int c0 = 0, c1 = 0, c2 = 0;
            for (int j = 1; j <= n; j++) {
                int s = a[r1][j] + a[r2][j];
                if (s == 0) c0++;
                else if (s == 1) c1++;
                else c2++;
            }
 
            long long totalPairs = 1LL * n * (n - 1) / 2;
 
            if (k == 0) {
                ans += totalPairs;
            }
 
            else if (k == 1) {
                ans += totalPairs - 1LL * c0 * (c0 - 1) / 2;
            }
 
            else if (k == 2) {
                ans += 1LL * c0 * c2
                     + 1LL * c1 * (c1 - 1) / 2
                     + 1LL * c1 * c2
                     + 1LL * c2 * (c2 - 1) / 2;
            }
 
            else if (k == 3) {
                ans += 1LL * c1 * c2
                     + 1LL * c2 * (c2 - 1) / 2;
            }
 
            else if (k == 4) {
                ans += 1LL * c2 * (c2 - 1) / 2;
            }
        }
	}
 
	cout << ans << xd;
}
 
signed main() {
    HuuThien();
	Sieve();
	int test;
	cin >> test;
	while(test--) {
		Init();
		Solve();
	}
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBGTkFNRSAiIgojZGVmaW5lIHhkICJcbiIKY29uc3QgaW50IE1BWE4gPSAoaW50KTUwNTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgbG9uZyBsb25nIE1PRCA9IChsb25nIGxvbmcpMWU5ICsgNzsKY29uc3QgaW50IElORiA9IChpbnQpMWU5Owpjb25zdCBpbnQgTElNID0gKGludCkyZTQgKyAxOwojZGVmaW5lIHVsbCB1bnNpZ25lZCBsb25nIGxvbmcKCnRlbXBsYXRlPGNsYXNzIFgsIGNsYXNzIFk+Cglib29sIG1pbmltaXplKFggJmEgLCBZIGIpIHsKCQlpZihhID4gYikgewoJCQlhID0gYjsKCQkJcmV0dXJuIHRydWU7CgkJfQoJCXJldHVybiBmYWxzZTsKCX07Cgp0ZW1wbGF0ZTxjbGFzcyBYLCBjbGFzcyBZPgoJYm9vbCBtYXhpbWl6ZShYICZhICwgWSBiKSB7CgkJaWYoYSA8IGIpIHsKCQkJYSA9IGI7CgkJCXJldHVybiB0cnVlOwoJCX0KCQlyZXR1cm4gZmFsc2U7Cgl9OwoKdm9pZCBIdXVUaGllbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOyBjb3V0LnRpZSgwKTsKCWlmKGZvcGVuKEZOQU1FIi5pbnAiLCAiciIpKSB7CgkJZnJlb3BlbihGTkFNRSIuaW5wIiwgInIiLCBzdGRpbik7CgkJZnJlb3BlbihGTkFNRSIub3V0IiwgInciLCBzdGRvdXQpOwoJfQp9CgppbnQgbSwgbiwgazsKdmVjdG9yPGJvb2w+IFByaW1lKChpbnQpMWU2ICsgMSwgdHJ1ZSk7CnZlY3Rvcjx2ZWN0b3I8aW50Pj4gYTsKCnZvaWQgU2lldmUoKSB7CglQcmltZVswXSA9IFByaW1lWzFdID0gZmFsc2U7Cglmb3IoaW50IGkgPSAyOyBpICogaSA8PSAoaW50KTFlNiA7IGkrKykgewoJCWlmKFByaW1lW2ldKSB7CgkJCWZvcihpbnQgaiA9IGkgKiBpOyBqIDw9IChpbnQpMWU2IDsgaiArPSBpKSB7CgkJCQlQcmltZVtqXSA9IGZhbHNlOwoJCQl9CgkJfQoJfQp9Cgp2b2lkIEluaXQoKSB7CgljaW4gPj4gbSA+PiBuID4+IGs7CglhLmFzc2lnbihtICsgMSwgdmVjdG9yPGludD4obiArIDEsIDApKTsKCglmb3IoaW50IGkgPSAxOyBpIDw9IG0gOyBpKyspIHsKCQlmb3IoaW50IGogPSAxOyBqIDw9IG4gOyBqKyspIHsKCQkJaW50IGFpOwoJCQljaW4gPj4gYWk7CgkJCWFbaV1bal0gPSBQcmltZVthaV07CgkJfQoJfQp9IAoKdm9pZCBTb2x2ZSgpIHsKCWxvbmcgbG9uZyBhbnMgPSAwOwoJZm9yIChpbnQgcjEgPSAxOyByMSA8PSBtOyByMSsrKSB7CiAgICAgICAgZm9yIChpbnQgcjIgPSByMSArIDE7IHIyIDw9IG07IHIyKyspIHsKICAgICAgICAgICAgaW50IGMwID0gMCwgYzEgPSAwLCBjMiA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAxOyBqIDw9IG47IGorKykgewogICAgICAgICAgICAgICAgaW50IHMgPSBhW3IxXVtqXSArIGFbcjJdW2pdOwogICAgICAgICAgICAgICAgaWYgKHMgPT0gMCkgYzArKzsKICAgICAgICAgICAgICAgIGVsc2UgaWYgKHMgPT0gMSkgYzErKzsKICAgICAgICAgICAgICAgIGVsc2UgYzIrKzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgbG9uZyBsb25nIHRvdGFsUGFpcnMgPSAxTEwgKiBuICogKG4gLSAxKSAvIDI7CgogICAgICAgICAgICBpZiAoayA9PSAwKSB7CiAgICAgICAgICAgICAgICBhbnMgKz0gdG90YWxQYWlyczsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgZWxzZSBpZiAoayA9PSAxKSB7CiAgICAgICAgICAgICAgICBhbnMgKz0gdG90YWxQYWlycyAtIDFMTCAqIGMwICogKGMwIC0gMSkgLyAyOwogICAgICAgICAgICB9CgogICAgICAgICAgICBlbHNlIGlmIChrID09IDIpIHsKICAgICAgICAgICAgICAgIGFucyArPSAxTEwgKiBjMCAqIGMyCiAgICAgICAgICAgICAgICAgICAgICsgMUxMICogYzEgKiAoYzEgLSAxKSAvIDIKICAgICAgICAgICAgICAgICAgICAgKyAxTEwgKiBjMSAqIGMyCiAgICAgICAgICAgICAgICAgICAgICsgMUxMICogYzIgKiAoYzIgLSAxKSAvIDI7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGVsc2UgaWYgKGsgPT0gMykgewogICAgICAgICAgICAgICAgYW5zICs9IDFMTCAqIGMxICogYzIKICAgICAgICAgICAgICAgICAgICAgKyAxTEwgKiBjMiAqIChjMiAtIDEpIC8gMjsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgZWxzZSBpZiAoayA9PSA0KSB7CiAgICAgICAgICAgICAgICBhbnMgKz0gMUxMICogYzIgKiAoYzIgLSAxKSAvIDI7CiAgICAgICAgICAgIH0KICAgICAgICB9Cgl9CgoJY291dCA8PCBhbnMgPDwgeGQ7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgSHV1VGhpZW4oKTsKCVNpZXZlKCk7CglpbnQgdGVzdDsKCWNpbiA+PiB0ZXN0OwoJd2hpbGUodGVzdC0tKSB7CgkJSW5pdCgpOwoJCVNvbHZlKCk7Cgl9Cn0K

Success #stdin #stdout 0.01s 5328KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/pHn3hK

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language