OrzPandaCup B项链 (群论+杜教筛)

题目大意：

一串形状为n*2的环形项链，由1*2的小矩形组成，求1~n本质不同的所有方案所需要的矩形数。经过旋转后相同的视为同一种方案。

题解：

显然这是等价类计数问题，我们需要先计算不考虑循环同构前的方案数f(n)。

所以我们要计算f(n)的表达式。如果没有环，那么方案数显然是斐波那契数列Fib(n)。有了环之后会增加两种情况。一种是两个矩形横跨起点，于是剩余空间是Fib(n-2)。另一种是两行中矩形错位排列，这种情况只在n为偶数时才可行，固定为2种方案。所以得到$$f(n)=Fib(n)+Fib(n-2)+2[n\%2==0], f(1)=1$$

然后根据Burnside引理，答案就是$$\sum_{m=1}^n\sum_{d|m}f(d)\varphi(n/d)$$本来Burnside引理计算环时要除以n，但题目中问的是矩形数量，刚好抵消了

然后发现这个算式的形式和推导杜教筛的式子是一样的。数论分块后，斐波那契数论的前缀和容易计算，phi的前缀和套用杜教筛即可，复杂度$O(n^{2/3})$。

$$
f(n)=Fib(n)+Fib(n-2)+2[n\%2==0], f(1)=1\\
Ans=\sum_{m=1}^n\sum_{d|m}f(d)\varphi(n/d)\\
=\sum_{d=1}^nf(d)\sum_{i=1}^{\lfloor n/d\rfloor}\varphi(i)\\
=\sum_{d=1}^n f(d) \Phi(\lfloor n/d\rfloor)
$$

```
#include <algorithm>
```
```
#include <cstdio>
```
```
#include <cstring>
```
```
#include <map>
```
```
#include <iostream>
```
```
using namespace std;
```
```
const int maxn = 2000010;
```
```
typedef long long ll;
```

ll T, pri[maxn], cur, mu[maxn], sum_mu[maxn], Fib[maxn];

```
bool vis[maxn];
```
```
map<ll, ll> mp_mu;
```
```
 
```
```
ll S_mu(ll x) {
```
```
  if (x < maxn) return sum_mu[x];
```
```
  if (mp_mu[x]) return mp_mu[x];
```
```
  ll ret = 1ll;
```

  for (ll i = 2, j; i <= x; i = j + 1) {

```
    j = x / (x / i);
```
```
    ret -= S_mu(x / i) * (j - i + 1);
```
```
  }
```
```
  return mp_mu[x] = ret;
```
```
}
```
```
ll S_phi(ll x) {
```
```
  ll ret = 0ll;
```

  for (ll i = 1, j; i <= x; i = j + 1) {

```
    j = x / (x / i);
```

    ret += (S_mu(j) - S_mu(i - 1)) * (x / i) * (x / i);

```
  }
```
```
  return ((ret - 1) >> 1) + 1;
```
```
}
```
```
int P;
```
```
void init(){
```
```
  mu[1] = 1;
```
```
  for (int i = 2; i < maxn; i++) {
```
```
    if (!vis[i]) {
```
```
      pri[++cur] = i;
```
```
      mu[i] = -1;
```
```
    }
```

    for (int j = 1; j <= cur && i * pri[j] < maxn; j++) {

```
      vis[i * pri[j]] = true;
```
```
      if (i % pri[j])
```
```
        mu[i * pri[j]] = -mu[i];
```
```
      else {
```
```
        mu[i * pri[j]] = 0;
```
```
        break;
```
```
      }
```
```
    }
```
```
  }
```

  for (int i = 1; i < maxn; i++) sum_mu[i] = sum_mu[i - 1] + mu[i];

```
  Fib[0]=Fib[1]=1;
```

  for (int i = 2; i < maxn; i++) Fib[i]=(Fib[i-1]+Fib[i-2])%P;

```
}
```
```
ll fib(ll n){
```
```
	if (n<maxn) return Fib[n];
```
```
    ll x=0,y=1,t;
```

    for (int d=62-__builtin_clzll(++n);d>=0;d--){

        t=(x*x+y*y)%P; y=(x+x+y)*y%P; x=t;

```
        if (n>>d&1) x=y,y=(t+y)%P;
```
```
    }
```
```
    return x;
```
```
}
```
```
ll S_F(ll x){
```
```
	if (x<2) return x;
```
```
	return (fib(x+2)+fib(x)+x-(x&1)-3)%P;
```
```
}
```
```
 
```
```
int main(){
```
```
 	ll n;
```
```
	scanf("%lld%lld",&n,&P);
```
```
	init();
```
```
	ll sum=0;
```
```
	for (ll i=1,j;i<=n;i=j+1){
```
```
		j=n/(n/i);
```

		//cout<<i<<' '<<S_F(j)-S_F(i-1)<<' '<<S_phi(n/i)<<'\n';

		sum+=(S_F(j)-S_F(i-1)+P)*S_phi(n/i)%P;

```
	}
```
```
	printf("%lld\n",sum%P);
```
```
   	return 0;
```
```
}
```

fffasttime

OrzPandaCup B项链 (群论+杜教筛)

1 评论

发表评论取消回复

1 评论

发表评论 取消回复

发表评论取消回复