题目描述
为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。
在晚宴上,主办方为大家提供了种不同的寿司,编号
,其中第
种寿司的美味度为
(即寿司的美味度为从
到
)。
现在小 G 和小 W 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 G 品尝的寿司种类中存在一种美味度为的寿司,小 W 品尝的寿司中存在一种美味度为
的寿司,而
与
不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数取模)。注意一个人可以不吃任何寿司。
输入格式
输入文件的第1行包含2个正整数,中间用单个空格隔开,表示共有
种寿司,最终和谐的方案数要对
取模。
输出格式
输出一行包含1个整数,表示所求的方案模的结果。
题目解析
转化一下题意,就是求小G和小W分别选择一个整数集合,使得不同集合间任意两数均互质的方案数。
考虑整数的质因数分解,两个整数互质当且仅当两者没有相同的质因子。如果我们将整数集合内所有整数所含的质因子表示为一个新集合
,集合
内所有整数所含的质因子表示为一个新集合
。可以知道若集合
满足题意,当且仅当
没有交集。
我们发现,对于任何小于的正整数,至多有一个
的质因子。如果有一个人选择了包含质因子
的整数,那么另一个人不能选取任何包含质因子
的整数。这启发我们将所有存在大质因子整数以它们的大质因子分类。同一类的整数只能被一个人选择。
因为的质因子只有
个,所以在没有大质因子的情况下,我们可以把一个人选择的质因子集合表示为一个
的二进制数
。设选择到第
个整数时小
选择的集合为
,小
选择的集合为
的方案数为
。则有
其中是整数
的质因子集合。上述方程显然是可以用滚动背包优化一维空间的。
考虑有大质因子的情况。假设我们现在考虑到质因子,另设
为大质因子分给小
,考虑到第
个整数时小
此时质因子集合为
,小
质因子集合为
的方案数,同理
为大质因子分给小
的方案数。则有
意义如上所述。同理,这个方程也可以优化掉一位空间。在开始一类数的DP时,我们先令
在DP完成后,再令
因为两个人均不选这类数的情况在和
中均出现了。
总时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
/************************************************************** Problem: 4197 User: frank_c1 Language: C++ Result: Accepted Time:660 ms Memory:4352 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=1<<9; unsigned f[maxn][maxn]; unsigned g[2][maxn][maxn]; int id[30],tb[]={2,3,5,7,11,13,17,19}; int pr[505],st[505],rk[505]; inline void calc(int n) { int k=n; REP(i,2,22) if(k%i==0) { st[n]|=1<<id[i]; while(k%i==0) k/=i; } pr[n]=k; } bool cmp(int i,int j) {return pr[i]<pr[j];} int main() { int mx=(1<<8)-1; REP(i,0,7) id[tb[i]]=i; int n,p;unsigned res=0; read(n);read(p); REP(i,2,n) calc(i),rk[i]=i; sort(rk+2,rk+n+1,cmp); f[0][0]=1; int now=1; REP(s,2,n) { int k=rk[s]; if(pr[k]!=1) break; PER(i,mx,0) PER(j,mx,0) if(!(i&j)) f[i|st[k]][j]+=f[i][j],f[i|st[k]][j]%=p; PER(i,mx,0) PER(j,mx,0) if(!(i&j)) f[i][j|st[k]]+=f[i][j],f[i][j|st[k]]%=p; } REP(s,2,n) { int k=rk[s]; if(pr[k]==1) continue; if(pr[k]!=now) { if(now!=1) REP(i,0,mx) REP(j,0,mx) if(!(i&j)) f[i][j]=(g[0][i][j]+g[1][i][j]-f[i][j]+p)%p; REP(c,0,1) REP(i,0,mx) REP(j,0,mx) if(!(i&j)) g[c][i][j]=f[i][j];now=pr[k]; } PER(i,mx,0) PER(j,mx,0) if(!((i|st[k])&j)) g[0][i|st[k]][j]+=g[0][i][j],g[0][i|st[k]][j]%=p; PER(i,mx,0) PER(j,mx,0) if(!(i&(j|st[k]))) g[1][i][j|st[k]]+=g[1][i][j],g[1][i][j|st[k]]%=p; } if(now!=1) REP(i,0,mx) REP(j,0,mx) if(!(i&j)) f[i][j]=(g[0][i][j]+g[1][i][j]-f[i][j]+p)%p; REP(i,0,mx) REP(j,0,mx) if(!(i&j)) res=(res+f[i][j])%p; printf("%u\n",res); return 0; } |