[洛谷 5746][NOI2002]机器人M号

题目链接

https://www.luogu.com.cn/problem/P5746

题解

显然，\(i\) 号机器人的独立数就是 \(\varphi(i)\)（特别地，\(1\) 号机器人的独立数为 \(0\)）。

政客和军人的独立数之和可以很容易用 DP 求出。

设 \(f(i,0/1)\) 表示前 \(i\) 个因子中，选了奇数个或偶数个因子的独立数的和。

对于当前因子有选和不选两种决策，所以有，

$$f(i,j)=f(i-1,j \oplus 1) \times \varphi(p_i) + f(i-1,j)$$

特别地，因为政客和军人的讨论范围都是奇素数，因此要对 \(p_i=2\) 的情况特殊处理。

最后用总独立数减去政客和军人的独立数即可得到学者的独立数。

总独立数并不难算，因为 \(m= \sum_{d|m} \varphi(d)\)，故总独立数为 \(m-1\)（别忘了 \(1\) 号机器人并不在我们的讨论范围之内）。

#include <cstdio>
#define MOD 10000
int f[1005][2];
int fpow(int x,int y)
{
 int ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
int main()
{
 int k;
 scanf("%d",&k);
 int tot=1;
 f[0][0]=1;
 for(int i=1;i<=k;i++)
 {
  int p,e;
  scanf("%d%d",&p,&e);
  tot=tot*fpow(p,e)%MOD;
  for(int j=0;j<=1;j++)
   f[i][j]=(f[i-1][j^1]*(p==2?0:p-1)+f[i-1][j])%MOD;
 }
 f[k][0]=(f[k][0]-1+MOD)%MOD;
 printf("%d\n",f[k][0]);
 printf("%d\n",f[k][1]);
 printf("%d\n",((tot-f[k][0]-f[k][1]-1)%MOD+MOD)%MOD);
 return 0;
}