1001:Couple doubi

暴力打表找规律可知，对于任意的p。

（1^i+2^i+...+(p-1)^i）%p=｛    

非0     ，i%（p-1)==0

 0        ,  i%(p-1)!=0

｝

所以，结果就很显然了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define eps 1e-4
#define zero(x) ((fabs(x)<eps)?0:x)
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        int x=n/(k-1);
        if(x%2==0)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

1004：Task

很显然，y对总值的影响远小于x。

所以：

按y排序，y小的放在前面，然后按x排序，x小的放在前面，然后按属性排序，任务放在前面。

然后依次遍历这些点。

如果当前点为任务：

把当前任务的价值放入set中。

如果当前点为机器：

在set中寻找最后一个比当前机器的价值小的任务。

#include <iostream>
#include<stdio.h>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
struct list
{
    int x;
    int y;
    int s;
    int leap;
    friend bool operator <(const list &a,const list &b)
    {
        if(a.y!=b.y)return a.y<b.y;
        else if(a.x!=b.x)return a.x<b.x;
        else return a.leap<b.leap;
    }
}node[220000];
multiset<int>st;
multiset<int>::iterator it;
int sea(int x)
{
    if(st.size()==0)return 0;
    it=st.begin();
    if(x<(*it))return 0;
    it=st.lower_bound(x);
    if(it==st.end())
    {
        it=st.end();
        it--;
        int ans=(*it);
        st.erase(it);
        return ans;
    }
    if((*it)==x)
    {
        st.erase(it);
        return x;
    }
    it--;
    int ans=(*it);
    st.erase(it);
    return ans;
}
void dos(int n)
{
    int x=0;
    LL sum=0;
    st.clear();
    for(int i=1;i<=n;i++)
    {
        if(node[i].leap==1)
        {
            int res=sea(node[i].s);
            if(res)
            {
                x++;
                sum+=(LL)res;
            }
        }
        else
        {
            st.insert(node[i].s);
        }
    }
    cout<<x<<" "<<sum<<endl;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&node[i].x,&node[i].y);
            node[i].leap=1;
            node[i].s=node[i].x*500+node[i].y*2;
        }
        for(int i=n+1;i<=n+m;i++)
        {
            scanf("%d%d",&node[i].x,&node[i].y);
            node[i].leap=0;
            node[i].s=node[i].x*500+node[i].y*2;
        }
        sort(node+1,node+n+m+1);
        for(int i=1;i<=n+m;i++)
        {
            //cout<<node[i].x<<" "<<node[i].y<<" "<<node[i].leap<<endl;
        }
        dos(n+m);
    }
    return 0;
}

wh[i][j]:天气为i，叶子的状态为j的概率。

ww[i][j]:今天天气为i，明天天气为j的概率。

st[i]:第一天天气为i的概率。

叶子的状态序列为{b1,b2...bn}

那么对于某个天气序列｛a1,a2....an}的概率为：

st[a1]*wh[a1][b1]* ww[a1][a2] *wh[a2][b2]* ww[a2][a3]* wh[a3][b3]*........*ww[an-1][an]*wh[an][bn];

因为结果有可能很小，所以用log把乘法转化为加法。

然后就是很明显的dp求路径了。。。。

#include <iostream>
#include<stdio.h>
#include<set>
#include<vector>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define LL long long
#define INF 99999999
#define eps 1e-6
#define zero(x) ((fabs(x)<eps)?0:x)
double wh[3][4]={
    {0.6,0.2,0.15,0.05},
    {0.25,0.3,0.2,0.25},
    {0.05,0.10,0.35,0.5}
};
double ww[3][3]={
    {0.5,0.375,0.125},
    {0.25,0.125,0.625},
    {0.25,0.375,0.375}
};
double st[3]={0.63,0.17,0.2};
double dp[55][3];
double ans[55][3];
vector<int>vec;
int a[110];
char str[110];
void dfs(int x,int y)
{
    //cout<<y<<endl;
    vec.push_back(y);
    if(x==1)
    {
        return ;
    }
    for(int i=2;i>=0;i--)
    {
        if(zero(ans[x][y]-(ans[x-1][i]+dp[x][y]+ww[i][y]))==0)
        {
            dfs(x-1,i);
            break;
        }
    }
}
int main()
{
    int T,cas,n;
    scanf("%d",&T);
    cas=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            ww[i][j]=log(ww[i][j]);
        }
    }
    while(T--)
    {
        vec.clear();
        cas++;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str);
            int x=strlen(str);
            if(x==3)a[i]=0;
            else if(x==6)a[i]=1;
            else if(x==4)a[i]=2;
            else if(x==5)a[i]=3;
        }
        memset(dp,0,sizeof(dp));
        double s=0;
        for(int i=1;i<=n;i++)
        {
            s=0;
            for(int j=0;j<3;j++)
            {
                dp[i][j]=wh[j][a[i]];
                s+=dp[i][j];
            }
            for(int j=0;j<3;j++)dp[i][j]=dp[i][j]/s;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<3;j++)
            {
                dp[i][j]=log(dp[i][j]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<3;j++)ans[i][j]=-INF;
        }
        for(int j=0;j<3;j++)
        {
            ans[1][j]=dp[1][j]+log(st[j]);
        }
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<3;j++)
            {
                for(int k=0;k<3;k++)
                {
                    double ps=ans[i-1][k]+ww[k][j]+dp[i][j];
                    ans[i][j]=max(ans[i][j],ps);
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<3;j++)
            {
               // cout<<ans[i][j]<<" ";
            }
         //   cout<<endl;
        }
        double maxx=-INF;
        int p=0;
        for(int j=0;j<3;j++)
        {
            if(maxx<ans[n][j])
            {
                maxx=ans[n][j];
                p=j;
             //   cout<<maxx<<" "<<p<<endl;
            }
        }
        dfs(n,p);
        printf("Case #%d:\n",cas);
        for(int i=n-1;i>=0;i--)
        {
            if(vec[i]==0)puts("Sunny");
            if(vec[i]==1)puts("Cloudy");
            if(vec[i]==2)puts("Rainy");
        }
    }
    return 0;
}

假如初始全部是正面（状态为0）。

全部操作完成后，正面的个数为x个。

那么x有很多种情况。假如分别为{x1,x2....xk}

那么结果为C(m,x1)+C(m,x2)+C(m,x3)+...+C(m,xk).

很明显可以得知x1,x2...xk奇偶性一致。

我们试验几组例子可知，x1,x2...xk是一段连续的区间。

那么我们只需要求出x1,xk就可以了。

然后我们就可以每走一步，根据上一步的x1,xk，确定这一步之后的x1,xk.

#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define LL long long
#define mod 1000000009
LL jie[110000];
void init()
{
    jie[0]=1;
    jie[1]=1;
    for(int i=2;i<=100000;i++)
    {
        jie[i]=jie[i-1]*i;
        jie[i]=jie[i]%mod;
    }
}
LL qmod(LL x,LL y)
{
    if(y==0)return 1;
    if(y==1)return x%mod;
    LL ans=qmod(x,y/2);
    ans=(ans*ans)%mod;
    if(y%2)ans=(ans*x)%mod;
    return ans;
}
LL dos(int n,int m)
{
    LL ans=jie[n];
    ans=(ans*qmod((jie[m]*jie[n-m])%mod,mod-2))%mod;
    return ans;
}
int main()
{
    init();
    int n,m,x;
    while(~scanf("%d%d",&n,&m))
    {
        int l,r;
        scanf("%d",&x);
        l=r=x;
        int ll,rr;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&x);
            ll=l-x;
            rr=r+x;
            if(ll<0)
            {
                if(r-x<0)ll=0+x-r;
                else ll=((l-x)%2+2)%2;
            }
            if(rr>m)
            {
                if(l+x<=m)rr=m-(r+x)%2;
                else rr=m-(l+x-m);
            }
            l=ll;
            r=rr;
        }
        LL ans=0;
        for(int i=l;i<=r;i+=2)
        {
            ans+=dos(m,i);
            ans=ans%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}