学步园

目测本月没有cf了，明天下午没课，补一场cf吧

A. Dreamoon and Stairs

n层楼梯，一次可以走1步或2步，要使总步数为m的倍数，求最少走多少步。     列方程联立，枚举

#include <cstdio>

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = m; i <= n; i += m) {
        if (2*i-n >= 0) {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

B. Dreamoon and WiFi

给一个只有'+','-'的序列，第二个序列含有‘+’，‘-’，‘？’，‘+'代表向前走，'-'代表向后走，’？‘有50%的概率向前，%50向后，求零点分别执行两个序列，求终点一样的概率

#include <cstdio>
#include <math.h>
#include <cstring>
const int N = 20;
char A[1000], B[1000];
int a[N][N];
void init() {
    a[0][0] = a[1][1] = a[1][0] = 1;
    for (int i = 2; i < N; i++)
        for (int j = 0; j <= i; j++)
            a[i][j] = a[i-1][j] + a[i-1][j-1];
}

int main() {
    init();
    scanf("%s%s", A, B);
    int add = 0, sub = 0;
    int len = strlen(A);
    for (int i = 0; i < len; i++) {
        if (A[i] == '+') add++;
        if (A[i] == '-') sub++;
    }
    for (int i = 0; i < len; i++) {
        if (B[i] == '+') add--;
        if (B[i] == '-') sub--;
    }
    if (add < 0 || sub < 0) {
        printf("0.0000000000000\n");
        return 0;
    }
    if (add == 0 && sub == 0) {
        printf("%.12f\n", 1.0000000000);
        return 0;
    }
    int what = add + sub;
    double ans = a[what][add]*1.0/(pow(2, what)*1.0);
    printf("%.12f\n", ans);
    return 0;
}

C. Dreamoon and Sums

给定a，b。求有多少个x，使x满足：x/b / x%b == k 且 a >= k>=1

题解: 设x/b = u, x%b = w, 则：1->x = b*u + w  由 x/b / x%b == k有：u/w = k, 即u = k*w带入1中
： x = b*k*w + w w的取值范围为[0,b-1],  x = b*(b-1)/2*(b*k+1),枚举k从1到a就好了（直接O(1)把方程解出来也行）

#include <cstdio>
const int MOD = (int) 1e9+7;
typedef long long LL;
int main() {
    __int64 a, b;
    scanf("%I64d%I64d", &a, &b);
    if (b == 1) {
        printf("0\n");
        return 0;
    }
    LL ans = 0;
    for (LL i = 1; i <= a; i++) {
        ans = (ans + b*(b-1)/2%MOD * ((1+i*b) %MOD) )% MOD;
    }
    printf("%I64d\n", ans%MOD);
    return 0;
}

D. Dreamoon and Sets

给出n，k。求出n个集合，每个集合含有4个元素，所有集合中的元素不重复，且在同一集合中，任意两个元素的最大公约数为k

构造（from九野）：1 2 3 5 这样一个最小的且互素的集合，如果要求多个就每个元素+6（贪心，加最小不重复的），输出的时候每个元素*k

#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
const int q = 6;

vector<int>G[10000];

void init(int x) {
    G[x].clear();
    if (x == 1) {
        G[x].pb(1);
        G[x].pb(2);
        G[x].pb(3);
        G[x].pb(5);
    }
    else {
        G[x].pb(G[x-1][0]+q);
        G[x].pb(G[x-1][1]+q);
        G[x].pb(G[x-1][2]+q);
        G[x].pb(G[x-1][3]+q);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        init(i);
    printf("%d\n", G[n][3]*m);
    for (int i = 1; i <=n; i++) {
        for (int j = 0; j < G[i].size(); j++) {
            printf("%d ", G[i][j]*m);
        }
        puts("");
    }
    return 0;
}