YeXiaoRain Blog

發表於 更新於 分類於 Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘

题目

https://projecteuler.net/problem=106

题目说，S(集合)表示集合元素的和

集合A如果它任何不相交的两个子集B和C，同时满足

  1. S(B) != S(C)
  2. 如果 B的元素个数比 C多，那么 S(B)>S(C)

那么A是满足题意的

问 现在 给了一个集合，元素个数是n且满足第二条，要测试多少对 子集， 才能判定它是满足题意的

然后举例

n=4 是25中的 1对

n=7 是 966中的70对

求 n=12 时 需要判断的是261625中的多少对

理解

我是没想到，还能在ProjectEuler练习语文

注意到 一对不相交子集 如果元素个数不同，那么满足2一定不满足1,所以，如果“可能”满足1,那么元素个数相等

那么首先说 n=4时25怎么来的

假设四个元素 且排序了的 {A,B,C,D}

一个元素的比对就是 3+2+1=6,

两个元素的比对 3 种

因为不相交 所以 3个以上元素的不比对

所以哪里来的 25呢？？？？？？？？？？？？

换个思路

假设比对是有序的也就是 x和y比，y和x比 算两种，那么方案数一定是2的倍数？也不会25？

再说先放弃不相交的性质，只要不相等就计数？

1
2
3
1个元素 3+2+1=6
2个元素 5+4+3+2+1 = 15
3个元素 3+2+1=6

就是出不来25啊

一个办法是结束吧，放弃吧，只去关心1是怎么来的

然后我甚至想到了勾股定理4x4+3x3=25 然而也不是

难道是没考虑2的时候，之考虑了不相交

1
2
3
4
1对比1 3+2+1=6
1对比2 4x3 = 12
1对比3 4x1 = 4
2对比2 3

还真的是25

按照这个思路，尝试一下n=7,是不是966

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1v1:6+5+4+3+2+1 = 21
1v2:7x15=105
1v3:7x20=140
1v4:7x15=105
1v5:7x6=42
1v6:7x1=7
2v2:6x(5x4/2)+5x(4x3/2)+4x(3x2/2)+3x(2x1/2) = 105
2v3:21x10=210
2v4:21x5=105
2v5:21x1=21
3v3:15x4+10*1=70
3v4:35x1=35

21+105+140+105+42+7+105+210+105+21+70+35=966

那么这样说真的就是这个值了，不过n=12时这个值并不需要我们求

解

然后我们来看看 什么是可能

n=4, {A,B,C,D}

个数不相等的两个子集 一定不等

1v1 一定不等

2v2有 AB vs CD , AC vs BD, AD vs BC, 而只有AD vs BC是“可能”的，前面两组根据大小偏序关系一定不等

没有3v3以及以上

那么对于任意n呢

先看看n=7，{ABCDEFG}

1v1老样子一定不等

还剩下2v2和3v3

对于 2v2，一定是 一个的最小到最大构成的区间，包含另一个，

1
2
3
4
5
6
7
8
9
10
11
12
BC为中间:1x4=4
BD为中间:1x3=3
BE为中间:1x2=2
BF为中间:1x1=1
CD为中间:2x3=6
CE为中间:2x2=4
CF为中间:2x1=2
DE为中间:3x2=6
DF为中间:3x1=3
EF为中间:4x1=4

4+3+2+1+6+4+2+6+3+4=35

对于3v3,

X1<Y1<X2<Y2<X3<Y3一定不行， 7个

X1<X2<X3<Y1<Y2<Y3一定不行， 7个

X1<X2<Y1<X3<Y2<Y3一定不行， 7个

X1<X2<Y1<Y2<X3<Y3一定不行， 7个

X1<Y1<X2<X3<Y2<Y3一定不行， 7个

所以可行的3v3是 70-5x7=35 个

总共 35+35是70个

那么根据上面看到 实际上，不可能就是

两个子集排序后，对应下标位置偏序一致

代码

还需要代码吗，这题核心是语文的阅读理解，猜作者的意图

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
#include <bits/stdc++.h>
using namespace std;

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

int ia = 0;
int a[20];
int ib = 0;
int b[20];

int possible = 0;

int N = 12;

bool test_possible(){
  if(ia != ib)return false;
  int gcnt=0;
  int lcnt=0;
  rep(i,0,ia){
    if(a[i]< b[i]){
      lcnt++;
    }else{
      gcnt++;
    }
  }
  return lcnt != 0 && gcnt != 0;
}

void tryidx(int index){
  if(index == N){
    possible += test_possible();
    return;
  }
  a[ia++] = index;
  tryidx(index+1);
  ia--;
  if(ia != 0){
    b[ib++] = index;
    tryidx(index+1);
    ib--;
  }

  tryidx(index+1);
}


int main(){
  cin>>N;
  tryidx(0);
  printf("%d\n",possible);
  return 0;
}

發表於 更新於 分類於 Disqus： 文章字數： 685 所需閱讀時間 ≈ 2 分鐘

题目

https://projecteuler.net/problem=122

Addition chain

理解

看起来是个描述很简洁的题目

但是 我以为能有什么 局部最优

所以想说 15=3x5,也就是做一次 变3的工作 再一次变5的工作

对于质数 = 1+它的分解

然而错了

想不出什么方法，翻了翻wiki找到了上面的Addition chain

说计算addition chains目前是一个 NP-complete 的问题

好像也并不能dp

于是考虑生成过程，写了一个树上爆搜。

也就是 每个节点的子节点 等于该节点和，该节点以及祖先节点的和

这样就是加法过程，每次新增的数都是最大的。 但是这种情况 其实没有考虑 A-B-C-D-(D+B)-(D+C) , 这样就不是最后一个增加？

这样算法，感觉是有bug的？

虽然这样的代码过了。

不过，我打出了 bfs的 元素个数，看得到仅仅200的数据。191， 已经下标达到了4053954。

然后 我对拍了一下数据，最小的一个不一致是23，需要6步，而我错误的dp是7步

7步: 1+1=2,2+2=4,4+1=5,5+5=10,10+1=11,11+11=22,22+1=23

6步: 1+1=2,2+2=4,4+1=5,5+4=9,9+9=18,18+5=23

代码

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
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
  ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD
  ll mod(ll v){return (v%MOD+MOD)%MOD;} // output
  ll gcd(ll a,ll b){return b == 0?a:gcd(b,a%b);}
};

// 错误的方法 start
ll dp[210];
int p[210];

void wayWrong(){
  p[1] = 1;
  rep(i,2,20){
    if(!p[i]){
      for(int j = i*i;j<=200;j+=i){
        if(!p[j]){
          p[j]= i;
        }
      }
    }
  }
  rep(i,2,201){
    if(!p[i]){
      dp[i] = 1+dp[i-1];
    }else{
      dp[i] = dp[p[i]] + dp[i/p[i]];
    }
  }
}

// 错误的方法 end

struct Node{
  int dep = 0 ;
  int val = 0;
  Node * fa = NULL;
};

const int N = 10000000;

Node nodes[N+10];

int leftcnt = 200 - 1 ;
ll ans[210];

int main(){
  int st = 0;
  int rear = 1;
  nodes[0].val = 1;
  while(st < rear){
    Node * p = &nodes[st];
    while(p != NULL){
      int newval = p->val + nodes[st].val;
      if(newval <= 200){
        if(ans[newval] == 0){
          printf("%d[dep:%d][bfs idx:%d]\n",newval,nodes[st].dep,rear);
          ans[newval] = nodes[st].dep + 1;
          leftcnt--;
          if(leftcnt == 0){
            break;
          }
        }
        nodes[rear].fa = &nodes[st];
        nodes[rear].dep = nodes[st].dep+1;
        nodes[rear].val = newval;
        rear++;
        if(rear > N){
          printf("leftcnt:%d\n",leftcnt);
          rep(i,1,201){
            if(!ans[i]){
              printf("noans:%lld\n",i);
            }
          }
          return 0;
        }
      }
      p=p->fa;
    }
    st++;
    if(leftcnt == 0){
      break;
    }
  }
  ll count = 0;
  rep(i,1,201){
    count += ans[i];
    // printf("%lld:%lld\n",i,ans[i]);
  }
  printf("%lld\n",count);
  return 0;
}

發表於 更新於 分類於 Disqus： 文章字數： 206 所需閱讀時間 ≈ 1 分鐘

很久没写提解，也没打比赛了，昨天做了个题

题目

https://ac.nowcoder.com/acm/contest/8282/D

题解

https://blog.nowcoder.net/n/aa0719c9f7d9481cb0f9f93eb5e8a866

收获

关于莫反之前写过文章了，也很容易可以预先处理所有mu[1~n]

这次根据题目总结一下莫反的思路吧。

和上次类似，其实核心两点

  1. 找到 $gcd(x,y) == 1$这样对应的表达式
  2. 这样的表达式意味着我们可以用 $\sum_{i|gcd(x,y)}{\mu(i)} = [gcd(x,y)==1]$的知识
  3. 变成了 多层求和公式以后，注意求和的约数遍历值，逐个相邻的求和向前移动这个约数遍历值
  4. 最后就能得到完全没有约数只有倍数的 求和式子，可以各种前缀和之类的处理了

發表於 更新於 分類於 Disqus： 文章字數： 714 所需閱讀時間 ≈ 2 分鐘

题目

啊 被牛客题目描述坑了，把关键信息藏在数据范围里，不过顺便学了一下莫队。

牛客题目https://ac.nowcoder.com/acm/contest/7079/A ， 知道真实题意以后是个水题

大意

指莫队要解决的问题不是牛客的题。

给长n的数组，没有改动，q次询问区间的不同值的个数

q和n都1e5

解法

我看到mex都很慌，这玩意虽然看上去是个质朴的东西，但涉及到的都不太好搞

上面 直接暴力，就 O(q n)。

莫队实际上就是 优雅的分块，然后再暴力。

  1. 离线请求。
  2. 根据请求的[左端点/sqrt(n), 右端点]排序
  3. 暴力求解

意味着，每次对于 左端点/sqrt(n)相同的时候， 时间复杂度= sqrt(n)*询问个数 + n

总时间复杂度 sqrt(n)*q + n*sqrt(n)

一些优化，通过奇偶 来决定右端点是 正序还是逆序列。

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)


const int MAXN = 30005; // 数组大小
const int MAXQ = 200005; // 询问次数
const int MAXM = 1000005; // 值记录

int sq; // sqrt(n);
struct query{ // 把询问以结构体方式保存
  int l, r, id;
  // 不是按照 l 第一序列，r第二序
  // 而是 l/sq 第一序，r第二序列，对于相同的l/sq 其中根据l/sq的奇偶性来决定r是正向序还是逆向序
  bool operator<(const query &o) const { // 重载<运算符，奇偶化排序
    // 这里只需要知道每个元素归属哪个块，而块的大小都是sqrt(n)，所以可以直接用l/sq
    if (l / sq != o.l / sq)
      return l < o.l;
    if (l / sq & 1)
      return r < o.r;
    return r > o.r;
  }
} Q[MAXQ];
int A[MAXN];// 原始数组
int ans[MAXQ]; // 离线结果
int Cnt[MAXM];
int cur;// 总计
int l = 1, r = 0; // 左右游标

void add(int p) {
  if (Cnt[A[p]] == 0)
    cur++;
  Cnt[A[p]]++;
}
void del(int p) {
  Cnt[A[p]]--;
  if (Cnt[A[p]] == 0)
    cur--;
}
ll read(){
  ll r;
  scanf("%lld",&r);
  return r;
}
int main() {
  int n = read();
  sq = sqrt(n);
  rep(i,1,n+1){
    A[i] = read();
  }
  int q = read();
  rep(i,0,q){
    Q[i].l = read();
    Q[i].r = read();
    Q[i].id = i; // 把询问离线下来
  }
  sort(Q, Q + q); // 排序
  // 每个 按 l/sq的区块分的区间内，r的总变化最多n, l的变化 = sqrt(n) * 个数
  // 总代价 = sum 所有区块的代价 = 区块数 * r的每个区块变化 + sqrt(n) * 总个数 = n^(3/2) + q * n^(1/2);
  rep(i,0,q){
    while (l < Q[i].l)
      del(l++);
    while (l > Q[i].l)
      add(--l);
    while (r < Q[i].r)
      add(++r);
    while (r > Q[i].r)
      del(r--);
    ans[Q[i].id] = cur; // 储存答案
  }
  rep(i,0,q){
    printf("%d\n", ans[i]); // 按编号顺序输出
  }
  return 0;
}

参考

各种莫队博文

發表於 更新於 分類於 Disqus： 文章字數： 953 所需閱讀時間 ≈ 3 分鐘

题目

https://projecteuler.net/problem=101

大意

给你一个多项式表达式

然后 只对前面几项 进行最小幂次拟合，拟合的函数第一个和原函数 不同的输出值的和

原题目很简单，11x11的Vandermonde矩阵求个逆矩阵，甚至都不用处理分数 就搞完了

hackerrank

然后我发现了这个

https://www.hackerrank.com/contests/projecteuler/challenges/euler101/problem

直接把 矩阵拉到了 3000x3000,然后 多项式的系数是 传入的

首先Vandermonde就需要一个高效求逆的办法，最后再O(n^2)算算

高效求逆?

为什么要, 因为 我们有了原表达式，要去做拟合 实际就是

${\begin{pmatrix}
{a_0}\\
{a_1}\\
{a_2}\\
{\vdots}\\
{a_{n-1}}\\
\end{pmatrix}
}^T\begin{pmatrix}
{1}&{1}&{\cdots}&{1}\\
{x_{0}}&{x_{1}}&{\cdots}&{x_{n-1}}\\
{x_{0}^2}&{x_{1}^2}&{\cdots}&{x_{n-1}^2}\\
{\vdots}&{\vdots}&{}&{\vdots}\\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{\cdots}&{x_{n-1}^{n-1}}\\
\end{pmatrix}={
\begin{pmatrix}
{y_0}\\
{y_1}\\
{y_2}\\
{\vdots}\\
{y_{n-1}}
\end{pmatrix}}^T$

要去计算 左侧的a,如果能快速求逆，那么有

${\begin{pmatrix}
{a_0}\\
{a_1}\\
{a_2}\\
{\vdots}\\
{a_{n-1}}\\
\end{pmatrix}}^T
={\begin{pmatrix}
{y_0}\\
{y_1}\\
{y_2}\\
{\vdots}\\
{y_{n-1}}
\end{pmatrix}}^T
\begin{pmatrix}
{1}&{1}&{\cdots}&{1}\\
{x_{0}}&{x_{1}}&{\cdots}&{x_{n-1}}\\
{x_{0}^2}&{x_{1}^2}&{\cdots}&{x_{n-1}^2}\\
{\vdots}&{\vdots}&{}&{\vdots}\\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{\cdots}&{x_{n-1}^{n-1}}\\
\end{pmatrix}^{-1}$

也就是求完逆以后，只需要O(n^2)来得到a

$V(x_0,x_1,\cdots ,x_{n-1})=\begin{bmatrix} {1}&{1}&{\cdots}&{1} \\
{x_{0}}&{x_{1}}&{\cdots}&{x_{n-1}}\\
{x_{0}^2}&{x_{1}^2}&{\cdots}&{x_{n-1}^2}\\
{\vdots}&{\vdots}&{}&{\vdots}\\
{x_{0}^{n-1}}&{x_{1}^{n-1}}&{\cdots}&{x_{n-1}^{n-1}}\\ \end{bmatrix}$

有 $ V(x_0,x_1,\cdots ,x_{n-1})=\prod _{n > i > j \geq 0}(x _{i}-x _{j})$

众所周知 $A^{-1} = \frac{1}{|A|} A^*$,然而 这暴力算是4次方复杂度，似乎比玩高斯消元3次方还要久

换个方法 拉格朗日插值

想法很简单 比如过点 (1,1) (4,7) (9,100)的二次函数

直接表达式$f(x) = k_1(x-4)(x-9)+k_2(x-1)(x-9) + k_3(x-1)(x-4)$

注意到x取其中一个点时，求和的表达式只有一个不为0

也很明显 $k_i = y_i\prod\limits_{j\not =i}\dfrac{1}{x_i-x_j}$

$f(x)=\sum\limits_{i=0}^ky_i\prod\limits_{j\not =i}\dfrac{x-x_j}{x_i-x_j}$, 也可以知道它的逆矩阵 就是求和每一部分 的展开式的系数，(令 $y = [0 … 0 1 0 … 0]$ 即可知

回到题目$x_i = i+1, y_i = \sum\limits_{p=0}^n A_p(i+1)^p$

$f(x)=\sum\limits_{i=0}^k[y_i\prod\limits_{j\not =i}\dfrac{x-j-1}{i-j}]$

注意到 我们其实只需要求 $f(k+1)$ , 计算 所有$y_i$ O(n^2), 但是右侧看似复杂的$x_i$乘积，因为这里的取值，变成了只需要做阶乘运算即可。可类似前缀和。 再配合一点乘法逆元即可

代码

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
N = 0
A = []
inv = []
po = []
poinv = []
MOD = 1000000007


def u(v):
    r = 0
    vi = 1
    for i in range(0, N+1):
        r += A[i] * vi
        r %= MOD
        vi *= v
        vi %= MOD
    return r


def init():
    # init inv
    global inv
    inv = []
    inv.append(0)
    inv.append(1)
    for i in range(2, N+10):
        inv.append(((MOD - MOD // i) * inv[MOD%i]) % MOD)
    # init power
    global po
    po = []
    po.append(1)
    for i in range(1, N+10):
        po.append( (po[i-1] * i) % MOD )

    global poinv
    poinv = []
    poinv.append(1)
    for i in range(1, N+10):
        poinv.append( (poinv[i-1] * inv[i]) % MOD )


def fitn(y, n):
    r = 0
    for i in range(1, n+1):
        mul = y[i-1]
        # 分子
        mul *= po[n] * inv[n+1-i]
        # 分母乘法逆元
        mul *= poinv[i-1] * poinv[n-i]
        if (n - i) % 2 == 1:
            mul *= -1
        mul %= MOD
        r += mul
        r %= MOD
    return (r+MOD)%MOD


def work():
    init()
    ans = 0
    y = []
    for v in range(1, N+1):
        arr.append(u(v))

    for i in range(1, N+1):
        r = fitn(y, i)
        print(r, end=' ')
        ans += r
    return ans


def pe():
    global N, A
    N = 10
    A = [1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1]
    print(work())


def main():
    global N, A
    N = int(input())
    A = list(map(int, input().split()))
    work()


# pe()
main()

至此 我们通过了较难版本的hackerrank 上的pe101

参考

http://www.vesnik.math.rs/vol/mv19303.pdf

https://proofwiki.org/wiki/Inverse_of_Vandermonde_Matrix

0%