【uoj129】 NOI2015—寿司晚宴

http://uoj.ac/problem/129 (题目链接)

题意

　　给出2~n这n-1个数，求选2个集合，使得从两集合中任意各选取1个数出来它们都互质。求方案数。

Solution

　　PoPoQQQ

细节

　　最后更新f的时候要取模再加模再取模，因为两个g加起来就是2P了，再加个P就加爆了→_→，我还是图样

代码

// uoj129

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#define LL long long

#define inf 2147483647

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=1010,maxs=1ll<<8;

int f[maxs][maxs],g[2][maxs][maxs],id[100],bin[30];

int n,P;

struct data {int s,k;}a[maxn];

bool cmp(data a,data b) {

	return a.k<b.k;

}

int main() {

	scanf("%d%d",&n,&P);

	id[2]=0,id[3]=1,id[5]=2,id[7]=3,id[11]=4,id[13]=5,id[17]=6,id[19]=7;

	bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;

	for (int i=2;i<=n;i++) {

		int x=i,y=2;

		while (x!=1 && y<20) {

			while (x%y==0) a[i-1].s|=bin[id[y]],x/=y;

			y++;

		}

		a[i-1].k=x;

	}

	sort(a+1,a+n,cmp);

	f[0][0]=1;

	for (int i=1;i<n;i++) {

		if (i==1 || a[i].k==1 || a[i].k!=a[i-1].k) {

			memcpy(g[0],f,sizeof(f));

			memcpy(g[1],f,sizeof(f));

		}

		for (int j=bin[8]-1;j>=0;j--)

			for (int k=bin[8]-1;k>=0;k--) {

				if (!(k&a[i].s)) (g[0][j|a[i].s][k]+=g[0][j][k])%=P;

				if (!(j&a[i].s)) (g[1][j][k|a[i].s]+=g[1][j][k])%=P;

			}

		if (i==n-1 || a[i].k==1 || a[i].k!=a[i+1].k)

			for (int j=0;j<bin[8];j++)

				for (int k=0;k<bin[8];k++)

					f[j][k]=((g[0][j][k]+g[1][j][k]-f[j][k])%P+P)%P;

	}

	int ans=0;

	for (int i=0;i<bin[8];i++)

		for (int j=0;j<bin[8];j++)

			if (!(i&j)) (ans+=f[i][j])%=P;

	printf("%d\n",ans);

	return 0;

}