codechef WALL

domen111

http://www.codechef.com/problems/WALL/
這題輸出會有浮點誤差的問題，不過明明就只是除以2而已，為什麼這樣也會有問題?
就因此損失了好幾分，寫了一個正確的解法結果只拿到和暴力解一樣的分數(好像和當時排名賽的狀況有點像)

[C++] 純文本查看 復制代碼

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll x[524298];
ll d[524298];
int p[524298];
ll h,n,m,a,b,ind;
ll recb,rece;
ll cal()
{
        x[0]=0;
        for(ll i=1;1;i++)
        {
                if(i>=n) return x[n-1];
                if(p[ind]!=-1)
                {
                        recb=p[ind]-1;
                        rece=i-1;
                        break;
                }
                x[i]=x[i-1]+d[ind];
                p[ind]=i;
                ind=(a*ind+b)%m;
        }
        ll dif=n-1-rece;
        ll rec=rece-recb;
        return x[rece] + dif/rec*(x[rece]-x[recb]) + (x[recb+dif%rec]-x[recb]);
}
int main()
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
                memset(p,-1,sizeof p);
                scanf("%lld %lld %lld %lld %lld %lld",&h,&n,&m,&a,&b,&ind);
                for(ll i=0;i<m;i++)
                        scanf("%lld",&d[i]);
                ll ans=cal()*h;
                printf("%lld.%lld\n",ans/2,ans%2*5);
//                printf("%.1lf\n",double(cal()*h)/2);
        }
}