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; }