牛客IOI周赛_牛客博客

A、夹娃娃

思路：前缀和，卡cin和cout。

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int n,k,l,r;
ll a[100005];
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]+=a[i-1];
    while(k--) {
        scanf("%d%d",&l,&r);
        printf("%lld\n",a[r]-a[l-1]);
    }
    return 0;
}

B、莫的难题

思路：给你一个数，用数字 $1\sim 5$ 表示，往年蓝桥杯有道题“年号字串”，是用字母 $A\sim Z$ 表示一个数，其实就是转为26进制，那这里就是5进制了。
需要注意的是，不管是那个题目，不管是蓝桥杯的26进制和这道题的5进制，是没有0的，也就是要考虑26的倍数和5的倍数.
解决方法就是，如果这一位是26或者5就向高位借1。 $fac[m]*fac[n-m]$ 在90%的数据里是会大于1e9的，也就是说在求快速幂的时候如果不先取余就会溢出，那么就只能a10%了。
Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll fac[106];
ll qpow(ll x,ll y){
     x %= mod;
    ll ans = 1;
    while(y){
        if(y&1) ans = ans*x%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return ans;
}
char mp[7]={'0','1','2','3','5','9'},a[15];
int pos;
void solve(int n,int flag) {
    n-=(flag==1);
    if(n>5) solve(n/5,n%5==0);
    if(n%5) n%=5;
    else n=5;
    a[pos++]=mp[n];
}
int main() {
    int t,n,m;
    fac[0]=1;
    for(int i=1;i<=105;++i) fac[i]=i*fac[i-1]%mod;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);    pos=0;
        ll ans=fac[n]*qpow(fac[m]*fac[n-m],mod-2)%mod;
        solve(ans,0);
        a[pos]='\0';
        puts(a);
    }
    return 0;
}

C、不平衡数组

待补

D、数列统计

打表：X=3
L=1:
ans=1
L=2：
ans=3=X
L=3
ans=3+2+1=x+...+1= $\frac{x*(x+1)}{2}$
L=4
ans= $\frac{x*(x+1)}{2}+\frac{(x-1)*x}{2}+...+1$ = $\frac{x*(x+1)*(x+2)}{6}$
L=5
可以根据前面的递推结果猜到现在应该是 $\frac{x*(x+1)*(x+2)*(x+3)}{24}$ ，验证后还真是，那么递推式就有了： $ans=\frac{(x+l-2)*(x+l-3)...(x+1)*x}{(l-1)!}$
组合数用逆元+阶乘求就可以了。
Code:

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 911451407;
const int maxn = 100005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll fac[2000005];
ll qpow(ll x,ll y){
     x %= mod;
    ll ans = 1;
    while(y){
        if(y&1) ans = ans*x%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return ans;
}
int main(){
    fac[0] = 1;
    for(int i = 1 ; i < 2000005 ; ++i) fac[i] = fac[i-1]*i%mod;
    int t = read();
    while(t--){
        ll l = read(),x= read();
        ll ans = fac[x+l-2]*qpow(fac[x-1],911451405)%mod;
        ans = ans*qpow(fac[l-1],911451405)%mod;
        cout<<ans<<endl;
    }
}