1001 Road To The 3rd Building

链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=884
题意：
T组输入，每一组给定长度为n的一组数列，对于该数列存在多组i,j满足1<=i<=j<=n,可以求得每一组a[i]~ a[j]的平均数，求这个平均数的数学期望
题解：
可以先分开讨论,设i~j包含的个数为k，那么k:1 ~n,一共存在的组数有n(n+1)/2.
k=1:a[1]+...+a[n];
k=2:a[1]+2a[2]+...+2a[n-1]+a[n];
k=3:a[1]+2a[2]+3a[3]+...+3a[n-2]+2a[n-1]+a[n];
k:...
k=n-2:a[1]+2a[2]+3a[3]+...+3a[n-2]+2a[n-1]+a[n];
k=n-1:a[1]+2a[2]+...+2a[n-1]+a[n];
k=n:a[1]+...+a[n];设右边的为ans
$图片说明$ 这就是所有组数之和了，/((n+1)n/2)就是数学期望了，因为这里有一个/k，所以需要进行一个线性预处理。

（少了一个负号）
除法取模：a/b%mod= $图片说明$ %mod
注意：
当n%2==1的时候，中间还有一个数据k=n/2+1要计算进去
代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans % mod;
}

//逆元函数 公式为 (a/b)%mod=(a*b^(mod-2))%mod
ll Inv(ll a, ll b) {
    return (a * quick_pow(b%mod, mod - 2)) % mod;//b->n*(n+1)/2可能会超过mod，所以要%mod
}

ll inv[maxn], a[maxn], f[maxn];

void init() {
    inv[1] = 1;
    for (ll i = 2; i < maxn; i++) {
        inv[i] = mod - mod / i * inv[mod % i] % mod;//使得结果为正,初始化，得到的就是1/i的逆元
    }
}

int main() {
    init();
    ll t;
    scanf("%lld", &t);
    f[0] = 0;
    while (t--) {
        ll ans = 0, n;
        scanf("%lld", &n);
        for (ll i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            f[i] = (f[i - 1] + a[i] % mod) % mod;//前缀和
        }
        ll k = 0;
        for (ll i = 1; i <= n / 2; i++) {
            k = (k + f[n - i + 1] - f[i - 1] + mod) % mod;//两个一起处理，因为i-1与n-i+1的系数是一样的都为这个k
            ans = (ans + k * inv[i] % mod) % mod;
            ans = (ans + k * inv[n - i + 1] % mod) % mod;
        }
        if (n % 2 == 1) {
            ans = (ans + (k + a[n / 2 + 1]) % mod * (inv[n / 2 + 1]) % mod) % mod;
        }
        ans = Inv(ans, n * (n + 1) / 2);
        printf("%lld\n", ans % mod);
    }
    return 0;
}

1002 Little Rabbit's Equation

链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=884
题意：
输入多个字符串，输出算式成立是在几进制下，若不存在输出-1
题解：
模拟暴力，遍历2~ 16进制，看等式是否成立
注意：
当运算为/时，必须整除才行,如7/2=3应该输出-1
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int main()
{
    char x[20];
    while(scanf("%s",x)!=EOF)
    {
        ll len=strlen(x);
        char ch;int  maxn=1, i,j;
        for(i=0;i<len;i++)
        {
            if(x[i]<='9'&&x[i]>='0')maxn=max(maxn,x[i]-'0');//找出最大的数字，则进制可能在maxn+1~16里头之中
            else if(x[i]<='F'&&x[i]>='A')maxn=max(maxn,x[i]-'A'+10);
            if(x[i]=='+'||x[i]=='-'||x[i]=='*'||x[i]=='/')ch=x[i];
        }
        int flag=0;
        for( i=maxn+1;i<=16;i++)
        {
            ll a=0,b=0,c=0,ab=-1;//i表示进制,j表示遍历
            j=0;
            for(j;j<len;j++)
            {
                if(x[j]<='9'&&x[j]>='0')a=x[j]-'0'+a*i;
                else if(x[j]<='F'&&x[j]>='A')a=a*i+x[j]-'A'+10;
                else break;
            }
            for(j+=1;j<len;j++)
            {
                if(x[j]<='9'&&x[j]>='0')b=x[j]-'0'+b*i;
                else if(x[j]<='F'&&x[j]>='A')b=b*i+x[j]-'A'+10;
                else break;
            }
            for(j+=1;j<len;j++)
            {
                if(x[j]<='9'&&x[j]>='0')c=x[j]-'0'+c*i;
                else if(x[j]<='F'&&x[j]>='A')c=c*i+x[j]-'A'+10;//可以乘以1LL*将int类型的数据转成ll型输出
                else break;
            }
            if(ch=='+')ab=a+b;
            else if(ch=='-')ab=a-b;
            else if(ch=='*')ab=a*b;
            else {
                if(a%b==0)ab=a/b;//得到的数都是整数
            }
            if(ab==c){flag=1;break;}
        }
        if(flag)printf("%d\n",i);
        else printf("-1\n");
    }
    return 0;
}

1006 A Very Easy Graph Problem（明天再补）

链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=884
题意：
题解：
注意：
代码：

1009 Divisibility

链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=884
题意：
T组数据，每一组数据给定一个b,x。任意的b进制的数y= $图片说明$ 若 $图片说明$ %x==0 ，则输出T，否则输出F
题解：
y= $图片说明$
当b=1时，成立，同理，当b%x==1时也成立
注意：
我当时理解错了，以为是把y转换成10进制，没想到是这几个数直接加起来%x,实力坑队友
代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
    int t;ll b,x;
    scanf("%d",&t);

    while(t--)
    {
        scanf("%lld%lld",&b,&x);
        if(b%x==1)printf("T\n");
        else printf("F\n");
    }
    return 0;
}

2020杭电多校第六场

1001 Road To The 3rd Building

1002 Little Rabbit's Equation

1006 A Very Easy Graph Problem（明天再补）

1009 Divisibility