E - Sum of gcd of Tuples (Hard)

题目大意：N个数，数的范围1~K，可以组成K^N个序列，求所有序列gcd的和。
算法：快速幂
思路：从序列->gcd->和这条线不好走，倒过来想，gcd有多少种可能？答案是从1到K。那对最大公约数i有几个？是不是也就是N个数中i的倍数有几个？答案是N/i。注意，最大公约数i的个数是不是包含2*i的个数，要减掉。
实现：从大大小找，因为大的要减小的，另外手写快速幂而不是直接pow()，因为会超范围。
代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>

#define LL  long long
#define MAXK    100010
#define P   1000000007
using namespace std;
int N, K;
LL cnt[MAXK];
LL ans = 0;
int main()
{
    scanf("%d%d", &N, &K);
    for(int i=K; i>=1; i--) {
        int t = K/i;
        cnt[i] = pow(t, N);
        for(int j=i+i; j<=K; j+=i) {
            cnt[i] -= cnt[j];
            cnt[i] %= P;
        }
//        printf("%d %d\n", i, cnt[i]);
        ans += cnt[i]*i;
        ans %= P;
    }
    cout << ans << endl;
    return 0;
}

F - Select Half

题目大意：从N个数中找个不相邻序列组成的最大和。
算法：dp
思路：先想出二维dp，设dp[i][j]: i个数中j个不相邻序列组成大最大值，dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i])，前面代表不取第i个数，后面代表取第i个数，要不相邻所以i-2。超时。只能减状态，i肯定不能，只能考虑j。
到第i个数，最多取个，题目最多，剩余N-i+1最多则，，最多三个状态。
实现：二维dp循环时注意j<=i/2，因为题目要求取N/2个。一维dp对于j只有三个状态，可以用map解决。
代码一O(n²):

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>

#define LL  long long
//#define MAXN    200010
#define MAXN    20010
#define P   1000000007
using namespace std;
int N;
int A[MAXN];
int dp[MAXN][MAXN/2];

int main()
{
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
    }    
    memset(dp, 0, sizeof(dp));
    dp[1][1] = A[1]; dp[2][1] = max(A[1], A[2]);
    for(int i=2; i<=N; i++) {
        for(int j=1; j<=i/2; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i]);

        }
    }
/*
    int i, j;
    i = N;j=N/2;
    cout<<"select:"<<endl;
    while(i&&j) {
        if(sel[i][j] != 0) {
            cout<<A[sel[i][j]]<<endl;
            i-=2;
            j-=1;
        }else {
            i-=1;
        }
    }
    */
    cout << dp[N][N/2] << endl;

    return 0;
}

代码二O(n)：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>

#define LL  long long
#define MAXN    200010
#define P   1000000007
using namespace std;
int N;
int A[MAXN];
map<int, LL> dp[MAXN];

//atcoder abs162-F
int main()
{
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
    }    
    dp[1][0] = 0; dp[1][1] = A[1];
    dp[2][0] = 0; dp[2][1] = max(A[1], A[2]);
    for(int i=3; i<=N; i++) {
        for(int j=i/2-1; j<=(i+1)/2; j++) {
            // 小心dp[i][j]   未被赋值默认0遇负数max可能出错
            if(dp[i-1].count(j)) {
                dp[i][j] = dp[i-1][j];
            }
            if(dp[i-2].count(j-1)) {
                if(!dp[i].count(j))
                    dp[i][j] = dp[i-2][j-1]+A[i];
                else dp[i][j] = max(dp[i][j], dp[i-2][j-1]+A[i]);
            }
        }
    }

    cout << dp[N][N/2]<<endl;
    return 0;
}

参考：
https://img.atcoder.jp/abc162/editorial.pdf