A - A Count Task

 HDU - 6480 

找出所有的区间只含一种字母。

注意long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e6+5;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        string s;
        cin>>s;
        ll len=s.size();
        ll  cur=0,ans=0,pos=0;
        for(ll i=0;i<len;i++){
            if(s[i]==s[pos]){cur++;}
            else if(s[i]!=s[pos]){pos=i;ans+=cur*(cur+1)/2;cur=1;}
        } 
        ans+=cur*(cur+1)/2;
        printf("%lld\n",ans);       
    }
    // system("pause");
    return 0;   
}

View Code

C - A Path Plan

 HDU - 6482 

组合计数；

考虑所有情况，Cc(x1+y1,x1)*Cc(x2+y2,x2)；

剔除相遇情况：Cc(x1+y2,x1)*Cc(x2+y1,x2)；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=2e5+6;
// const ll mod=998244353;
ll fac[N],inv[N];
ll pow_mod(ll a,ll n)
{
    ll ret =1;
    while(n)
    {
        if(n&1) ret=ret*a%mod;
          a=a*a%mod;
          n>>=1;
    }
    return ret;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
}
ll Cc(ll x, ll y)
{
    return fac[x]*pow_mod(fac[y]*fac[x-y]%mod,mod-2)%mod;
}
int main(){
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        int x1,x2,y1,y2;
        scanf("%d %d %d %d",&x1,&x2,&y1,&y2);
        ll a=(Cc(x1+y1,x1)*Cc(x2+y2,x2))%mod;
        ll b=(Cc(x1+y2,x1)*Cc(x2+y1,x2))%mod;
        ll ans=(a-b+mod)%mod;
        printf("%lld\n",ans);
    }
    // system("pause");
    return 0;
}

View Code