求 hack
查看原帖
求 hack
307940
aaaaaaaawsl楼主2022/11/12 18:46

这份代码,在72行进行的不是赋值操作而是累加操作,但是能过,求组数据hack掉它。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int mod = 1000000007;
const int N = 20;
const int M = (1 << 19);

int n, m, mx;
int a[18][18];
int tw[N];
int f[18][18][M];
int f2[18][18][M];

namespace FastIO {
    char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = ' ';
    long long p, p3 = -1;
    void read() {}
    void print() {}
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline void flush() {
        fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
       
    }
    template <typename T, typename... T2>
    inline void read(T &x, T2 &...oth) {
        long long f = 0;
        x = 0;
        char ch = getc();
        while (!isdigit(ch)) {
            if (ch == '-') f = 1;
            ch = getc();
        }
        while (isdigit(ch)) {
            x = (x << 1) + (x << 3) + (ch ^ '0');
            ch = getc();
        }
        x = f ? -x : x;
        read(oth...);
    }
    template <typename T, typename... T2>
    inline void print(T x, T2... oth) { 
        if (p3 > 1 << 20) 
            flush();
        if (x < 0)
            buf2[++p3] = 45, x = -x; 
        do {
            a[++p] = x % 10 + 48;
        } while (x /= 10);
        do {
            buf2[++p3] = a[p];
        } while (--p);
        buf2[++p3] = hh; 
        print(oth...);
    }
}
#define read FastIO::read
#define print FastIO::print

inline int Mod(int a){
	return (a >= mod ? a - mod : a);
}

void dp(){
	f[0][m][0] = 1;
	for(int i = 1; i <= n; ++ i){
		for(int j = 0; j <= mx; ++ j) f[i][0][j << 1] = f[i - 1][m][j];
		for(int j = 1; j <= m; ++ j){
			for(int k = 0; k <= mx; ++ k){
				int bit = k;
				int num = f[i][j - 1][bit];
				if(num == 0) continue; // 非法状态 
				int b1 = (bit >> (j - 1)) % 2, b2 = (bit >> (j)) % 2;
				
				if(!a[i][j]){
					if(!b1 && !b2) f[i][j][bit] = Mod(f[i][j][bit] + num);
				}
				
				else if(!b1 && !b2){
					f[i][j][bit] = Mod(f[i][j][bit] + num);
					if(a[i + 1][j]) f[i][j][bit + tw[j - 1]] = Mod(f[i][j][bit + tw[j - 1]] + num);
					if(a[i][j + 1]) f[i][j][bit + tw[j]] = Mod(f[i][j][bit + tw[j]] + num); 
				}
				
				else if(b1 && !b2){
					f[i][j][bit - tw[j - 1]] = Mod(f[i][j][bit - tw[j - 1]] + num);
				}
				
				else if(!b1 && b2) {
					f[i][j][bit - tw[j]] = Mod(f[i][j][bit - tw[j]] + num);
				}
				
			}
		}
	}
}

void dp2(){
	f2[n + 1][1][0] = 1;
	for(int i = n; i >= 1; -- i){
		for(int j = 0; j <= mx; ++ j) f2[i][m + 1][j >> 1] += f2[i + 1][1][j];
		for(int j = m; j >= 1; -- j){
			for(int k = 0; k <= mx; ++ k){
				int bit = k; int num = f2[i][j + 1][bit];
				if(num == 0) continue; // 非法状态 
				int b1 = (bit >> (j - 1)) % 2, b2 = (bit >> (j)) % 2;
				
				if(!a[i][j]){
					if(!b1 && !b2) f2[i][j][bit] = Mod(f2[i][j][bit] + num);
				}
				
				else if(!b1 && !b2){
					f2[i][j][bit] = Mod(f2[i][j][bit] + num);
					if(a[i - 1][j]) f2[i][j][bit + tw[j]] = Mod(f2[i][j][bit + tw[j]] + num);
					if(a[i][j - 1]) f2[i][j][bit + tw[j - 1]] = Mod(f2[i][j][bit + tw[j - 1]] + num); 
				}
				
				else if(b1 && !b2){
					f2[i][j][bit - tw[j - 1]] = Mod(f2[i][j][bit - tw[j - 1]] + num);
				}
				
				else if(!b1 && b2) {
					f2[i][j][bit - tw[j]] = Mod(f2[i][j][bit - tw[j]] + num);
				}
				
			}
		}
	}
}

int ans[20][20];

signed main(){
	read(n); read(m);
    for(int i = 1; i <= n; ++ i){
    	for(int j = 1; j <= m; ++ j){
    		read(a[i][j]);
    		a[i][j] ^= 1;
		}
	}
	tw[0] = 1;
	mx = (1 << (m + 1)) - 1;
	for(int i = 1; i <= 17; ++ i) tw[i] = tw[i - 1] << 1;
	dp();
	dp2();
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j){
			if(!a[i][j]) continue;
			int now = mx ^ (1 << (j - 1)) ^ (1 << j);
			for(int k = now; k; k = (k - 1) & now)
				ans[i][j] = Mod(ans[i][j] + (1ll * f[i][j - 1][k] % mod * f2[i][j + 1][k] % mod) % mod);
			ans[i][j] = Mod(ans[i][j] + (1ll * f[i][j - 1][0] % mod * f2[i][j + 1][0] % mod) % mod);
		}
	}
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j) print(ans[i][j]);
		FastIO :: flush();
		printf("\n");
	}
	return 0;
}
2022/11/12 18:46
加载中...