Road To The 3rd Building
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6827
比赛时一时半会没搞明白怎么下手,后来官方题解也看不太懂,还好后来找到了一份勉强能看明白的题解,菜鸡补题都这么艰难😭
这题首先是要确定分数的底数相同,具体操作可以假设一个较小的n,然后画图推演即可。
定义:a[]为输入数组;sum[]为a[]的前缀和;sumx[]为sum[]的前缀和;sumy[]为a[]的后缀和;sumk[]为sumy[]的后缀和;
可得规律:ans=sum[n]*k-sumx[k-1]-sumk[k-1];(计算时,注意加mod再取模。防止出现负数)

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=2e5+20;
const ll mod=1000000007;
ll sum[maxn],a[maxn];
ll ksm(ll a,ll b){
    a%=mod;
    ll ans=1;
    while(b){
        if(b&1)    ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll sumx[maxn],sumy[maxn],sumk[maxn];
int main(){
    ll t,n,ans;
    scanf("%lld",&t);
    while(t--){
        memset(sum,0,sizeof sum);
        memset(sumx,0,sizeof sumx);
        memset(sumy,0,sizeof sumy);
        memset(sumk,0,sizeof sumk);
        scanf("%lld",&n);
        ans = 0;
        for (ll i=1;i<=n;i++)        scanf("%lld",&a[i]),sum[i]=(sum[i-1]+a[i])%mod;
        for (ll i=1;i<=n;i++)        sumx[i]=(sumx[i-1]+sum[i])%mod;
        ll k=n;
        for (ll i=1;i<=n;i++)        sumy[i]=(sumy[i-1]+a[k])%mod,k--;
        for (ll i=1;i<=n;i++)        sumk[i]=(sumk[i-1]+sumy[i])%mod;
        for (ll i=1;i<=n;i++)        ans=(ans+((((i*sum[n]%mod)-sumx[i-1]-sumk[i-1]+mod)%mod)*ksm(i,mod-2)%mod))%mod;
        ll np=(((n+1)*n)/2)%mod;
        printf("%lld\n",((ans%mod)*(ksm(np,mod-2)%mod)%mod));
    }
    return 0;
}

Divisibility
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6835
题目看着比较吓人,判断下面定理是否正确:如果y%x=0,那么f(f(⋯f(y)⋯)%x=0
f(y)表示所有位数之和。
归结起来,就是y%x=0,那么f(y)%x=0
分析样例可得10%3=1,详细证明就不挂上来了,比较麻烦。刚开始比较困惑的一个点是没看懂题目,尤其是那个上面一条横线的式子看不懂啥意思。

#include<bits/stdc++.h>
using namespace std;
long long n,b,x;
int main(){
    scanf("%lld",&n);
    while(n--){
        scanf("%lld%lld",&b,&x);
        if((b-1)%x==0)
            printf("T\n");
        else
            printf("F\n");
    }
    return 0;
}