POJ1288 Sly Number(高斯消元 dfs枚举)

由于解集只为{0, 1, 2}故消元后需dfs枚举求解

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 60, INF = 0x3F3F3F3F; int a[N][N], mod;
int x[N];
int n, row;
int ans[N];
bool ok; int gauss(int a[][N], int n){
int i, j;
for(i = 0, j = 0; i < n && j < n; i++, j++){
int r = i;
for(int k = i; k < n; k++){
if(a[k][j]){
r = k;
break;
}
}
if(a[r][j] == 0){
i--;
continue;
}
if(r != i){
for(int k = 0; k <= n; k++){
swap(a[i][k], a[r][k]);
}
}
for(int k = i + 1; k < n; k++){
if(a[k][j]){
int x1 = a[i][j], x2 = a[k][j];
for(int l = j; l <= n; l++){
a[k][l] = (a[k][l] * x1 - x2 * a[i][l]) % mod;
}
}
}
}
return i;
} void dfs(int r){
if(r == -1){
ok = 1;
return;
}
if(ok){
return;
}
int x = 0;
while(x < n && a[r][x] == 0){
x++;
}
if(x == n){
if(a[r][n]){
return;
}
for(ans[x] = 0; ans[x] <= 2; ans[x]++){
dfs(r - 1);
}
return;
}
int tp = 0;
for(int j = x + 1; j < n; j++){
tp += a[r][j] * ans[j];
tp %= mod;
}
for(ans[x] = 0; ans[x] <= 2; ans[x]++){
if((ans[x] * a[r][x] + tp - a[r][n]) % mod == 0){
dfs(r - 1);
}
}
} int main(){
int t;
cin>>t;
while(t--){
cin >> mod >> n;
for(int i = 0; i < n; i++){
cin >> x[i];
}
for(int i = 0; i < n; i++){
a[i][n] = (i == 0);
for(int j = 0, k = i; j <= i; j++ , k--){
a[i][j] = x[k];
}
for(int j = i + 1, k = n -1; j < n; j++, k--){
a[i][j] = x[k];
}
}
row = gauss(a, n);
ok = 0;
dfs(n - 1);
if(ok){
printf("A solution can be found\n");
}else{
printf("No solution\n");
} } return 0;
}

  

上一篇:HDU - 6444 Neko's loop(循环节+最大子段和)


下一篇:vim 使用学习操作