NFLS-DAY 14

Posted on By 张, 高畅 NFLS-DAY 14无评论

T0

今天学习高斯消元&线性基
两者代码不长，但是有点复杂。

T1

给出一N个元线性非齐次方程组，共包含M个方程
求解这个方程组

模板题，但是有很多细节。

#include <bits/stdc++.h>
using namespace std;
long double a[1005][1005];
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n + 1; j++) cin >> a[i][j];
    }
    int cur = 1;
    for (int i = 1; i <= n; i++) {
        int id = cur;
        for (int j = cur; j <= m; j++) {
            if (fabs(a[j][i]) > fabs(a[id][i]))
                id = j;
        }
        if (fabs(a[id][i]) > 1e-10)
            for (int j = i; j <= n + 1; j++) swap(a[id][j], a[cur][j]);
        else
            continue;
        for (int j = n + 1; j >= i; j--) a[cur][j] /= a[cur][i];
        for (int j = 1; j <= m; j++) {
            for (int k = n + 1; k >= i; k--)
                if (j != cur)
                    a[j][k] -= a[j][i] * a[cur][k];
        }
        cur++;
    }
    for (int i = cur; i <= m; i++) {
        if (fabs(a[i][n + 1]) >= 1e-10) {
            cout << "No solutions";
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (fabs(a[i][i]) < 1e-10 && fabs(a[i][n + 1]) < 1e-10) {
            cout << "Many solutions";
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) cout << (int)(a[i][n + 1] / a[i][i] + 0.5) << endl;
    return 0;
}

T2

LUOGU
设球心坐标(x1,x2,x3,…xn)
对于第i(1<=i 给出N个整数，从中选出个或者多个，使得选出的整数乘积是完全平方数。一共有多少种选法？

对于"完全平方数"，很显然有一个分解质因数，由题目，保证因子不大于500，所以就应该是线性筛/埃氏筛。
接下来，对于每一个X，分解质因数。对于每一个因子，将它的数量异或起来，就可以得到一个方程。
然后就有就得到了n个方程组，用高斯消元解异或线性方程组，就可以了。

#include <bits/stdc++.h>
using namespace std;
int n;
typedef long long LL;
int primes[505], st[505], cnt = 0;
int a[505][505];
void init() {
    st[0] = st[1] = 1;
    for (int i = 2; i <= 500; i++) {
        if (!st[i])
            primes[++cnt] = i;
        for (int j = 1; primes[j] <= n / i; j++) {
            st[primes[j] * i] = 1;
            if (!(i % primes[j]))
                break;
        }
    }
}
LL gauss() {
    int i = 1, j = 1;
    for (; i <= n && j <= cnt; j++) {
        int t = i;
        for (; t <= n; t++) {
            if (a[t][j])
                break;
        }
        if (t <= n) {
            for (int k = 0; k <= cnt; k++) swap(a[i][k], a[t][k]);
            for (int k = 0; k <= n; k++) {
                if (i != k && a[k][j]) {
                    for (int l = 0; l <= cnt; l++) a[k][l] ^= a[i][l];
                }
            }
            i++;
        }
    }
    for (int k = i; k < n; k++) {
        if (a[k][cnt])
            return 0;
    }
    return 1LL << (n - i + 1);
}
void work() {
    scanf("%d", &n);
    memset(a, 0, sizeof a);
    for (int i = 1; i <= n; i++) {
        LL x;
        scanf("%lld", &x);
        for (int j = 1; j <= cnt; j++) {
            while (!(x % (LL)primes[j])) {
                a[i][j] ^= 1;
                x /= (LL)primes[j];
            }
        }
    }
    printf("%lld\n", gauss() - 1);
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--) work();
    return 0;
}

T6

LUOGU
线性基是一种擅长处理异或问题的数据结构.
这是一道模板题。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, k;
LL a[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int i = 62; ~i; i--) {
        for (int j = k; j < n; j++) {
            if (a[j] >> i & 1) {
                swap(a[j], a[k]);
                break;
            }
        }
        if (!(a[k] >> i & 1))
            continue;
        for (int j = 0; j < n; j++) {
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        }
        k++;
        if (k == n)
            break;
    }
    LL res = 0;
    for (int i = 0; i < k; i++) res ^= a[i];
    printf("%lld", res);
    return 0;
}

T7

ACWING

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, m;
LL a[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    int k = 0;
    for (int i = 62; ~i; i--) {
        for (int j = k; j < n; j++) {
            if (a[j] >> i & 1) {
                swap(a[j], a[k]);
                break;
            }
        }
        if (!(a[k] >> i & 1))
            continue;
        for (int j = 0; j < n; j++) {
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        }
        k++;
        if (k == n)
            break;
    }
    reverse(a, a + k);
    scanf("%d", &m);
    while (m--) {
        LL x;
        scanf("%lld", &x);
        if (k < n)
            x--;
        if (x >= (1LL << k))
            puts("-1");
        else {
            LL res = 0;
            for (int i = 0; i < k; i++) {
                if (x >> i & 1)
                    res ^= a[i];
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}

T8

LUOGU
先求出V的线性基。
然后我们会得到一个结论：每个数都出现一样的次数, 且这个次数为
2^(n-V的线性基)

#include<bits/stdc++.h>
using namespace std;
const int N=105,mod=10086;
int n,x,a[N],res=1,ans,base=1;
void insert(int x)
{
    for(int i=30;~i;i--)
    {
        if(!((1<<i)&x))continue;
        if(!a[i])
        {
            a[i]=x;
            break;
        }   
        x^=a[i];
        if(!x)
        {
            (res<<=1)%=mod;
            break;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert(x);  
    }
    scanf("%d",&x);
    for(int i=0;i<=30;i++)
    {
        if(a[i])
        {
            if((x>>i)&1)ans+=base;
            base<<=1;
        }
    }
    ans%=mod;
    printf("%d\n",(res*ans+1)%mod);
    return 0;
}
训练日志

发表回复