今日题解------codeforces 895C

题意：给你一个数列，然后找任意数量的数字（除了空集），使得他们的乘机为一个数的平方

我们发现元素最大70，所以我们可以从这里入手，平方数有个性质就是它的所有质因子的指数为偶数

比如：36 = 2*2*3*3；然后我们可以写一个状态压缩dp，第一维表示小于等于第一维的所有数字，第二

维表示到达的状态，那最终的结果就是dp[70][0]，dp[i]和dp[i-1]的区别就是，你有没有取到i这个数字，你会发现，

如果你取偶数个i的话，对于状态是不影响的，因为偶数个异或就是零，奇数个的话就是它的本身，里面还有一个性质，

就是C（n，0）+C（n，2） + ... = C（n，1）+C（n，3）+ ...，你可以取a=1，b=-1就很好证明，还有因为它们的和就是

2的n次方，参考https://zhidao.baidu.com/question/2268538776712429868.html（来自百度），所以无论取奇数个还是偶数，都有

2的n-1次方种，所以转移方程为if(cnt【i】) dp【i】【j】= (dp【i-1】【j】+ dp【i-1】【s【i】^ j】)*m【cnt【i】-1】；else dp【i】【j】 =dp【i-1】【j】；（还没加入取模运算）

下面直接看代码：

#include<bits/stdc++.h>

#define de(x) cout<<#x<<"="<<x<<endl;

#define dd(x) cout<<#x<<"="<<x<<" ";

#define rep(i,a,b) for(int i=a;i<(b);++i)

#define repd(i,a,b) for(int i=a;i>=(b);--i)

#define mt(a,b) memset(a,b,sizeof(a))

#define fi first

#define se second

#define inf 0x7f

#define pii pair<int,int>

#define pdd pair<double,double>

#define pdi pair<double,int>

#define mp(u,v) make_pair(u,v)

#define sz(a) a.size()

#define ull unsigned long long

#define ll long long

#define pb push_back

#define PI acos(-1.0)

const int mod = 1e9+;

const int maxn = 1e5+;

const double EPS = 1e-;

using namespace std;

int gcd(int a,int b){

    return b==?a:gcd(b,a%b);

}

int a[maxn];

int s[maxn];

int prime[maxn];

ll m[maxn];

int dp[][<<];

int cnt[];

bool is_prime(int x){

    for(int i=;i*i<=x;++i) if(x%i==) return false;

    return true;

}

void init(){

    mt(cnt,);

    int cntt = ;

    rep(i,,){

        if(is_prime(i)) prime[cntt++] = i;

    }

    m[] = ;

    rep(i,,maxn) m[i] = (m[i-]*)%mod;

    rep(i,,){

        int t = i;

        rep(j,,){

            while(t&&t%prime[j]==){

                 t/=prime[j];

                 s[i] = s[i]^(<<j);

            }

        }

    }

}

int main()

{

    init();

    int n;

    scanf("%d",&n);

    rep(i,,n){

        scanf("%d",&a[i]);

        cnt[a[i]]++;

    }

    dp[][] = ;

    rep(i,,){

        rep(j,,(<<)){

            if(cnt[i]){

                dp[i][j] = ((dp[i-][j] + dp[i-][j^s[i]]) %mod) * m[cnt[i]-]%mod;

            }else dp[i][j] = dp[i-][j];

        }

    }

    cout<<((dp[][]-+mod)%mod)<<endl;

    return ;

}

巴特西

今日题解------codeforces 895C

最新文章

热门文章