单选错位

单选错位

题目描述

gx和lc去参加noip初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。试卷上共有n道单选题，第i道单选题有ai个选项，这ai个选项编号是1,2,3,…,ai，每个选项成为正确答案的概率都是相等的。lc采取的策略是每道题目随机写上1-ai的某个数作为答案选项，他用不了多少时间就能期望做对（ai分之一求和）道题目。gx则是认认真真地做完了这n道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第i道题目的答案抄到了答题纸上的第i+1道题目的位置上，特别地，第n道题目的答案抄到了第1道题目的位置上。现在gx已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被lc鄙视了。

我们假设gx没有做错任何题目，只是答案抄错位置了。

输入格式

n很大，为了避免读入耗时太多，输入文件只有5个整数参数n, A, B, C, a1，由上交的程序产生数列a。下面给出C/C++的读入语句和产生序列的语句（默认从标准输入读入）：

// for C/C++
scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
for (int i=2;i<=n;i++)
a[i] = ((long long)a[i-1] * A + B) % 100000001;
for (int i=1;i<=n;i++)
a[i] = a[i] % C + 1;

选手可以通过以上的程序语句得到n和数列a（a的元素类型是32位整数），n和a的含义见题目描述。

输出格式

输出一个实数，表示gx期望做对的题目个数，保留三位小数。

样例

样例输入

3 2 0 4 1

样例输出

1.167

样例说明

a[] = {2,3,1}

共有6种情况，每种情况出现的概率是1/6，gx期望做对(3+1+1+1+1+0)/6 = 7/6题。（相比之下，lc随机就能期望做对11/6题）

数据范围与提示

对于30%的数据 n≤10, C≤10

对于80%的数据 n≤10000, C≤10

对于90%的数据 n≤500000, C≤100000000

对于100%的数据 2≤n≤10000000, 0≤A,B,C,a1≤100000000

FIRST

我只想到了DFS

#include 

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 3e5 + 4;
const int maxm = 9e4 + 10;

int n, A, B, C, a[maxn], b[maxn], c[maxn];
ll sum = 1, ans;
double p[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

ll check()
{
    ll ans = 0;
    /*printf("\nbbb\n");
    for(int i=1; i<=n; i++)
    {
        printf("%d ", b[i]);
    }
    printf("\nccc\n");
    for(int i=1; i<=n; i++)
    {
        printf("%d ", c[i]);
    }*/
    for(int i=1; i<=n; i++)
    {
        if(b[i] == c[i]) ans++;
    }
    return ans;
}

ll dfs(int now, int n)
{
    ll ans = 0;
    if(now > n)
    {
        return check();
    }
    for(int i=1; i<=a[now]; i++)
    {

        if(now != n)
        {
            b[now+1] = i;
            //printf("b[%d] == %d\n", now+1, b[now+1]);
        }
        else
        {
            b[1] = i;
            //printf("b[1] == %d\n", b[1]);
        }
        //printf("nonono %d %d\n", now+1, n+1);
        //printf("b[%d] == %d\n", (now+1)%(n+1), b[(now+1)%(n+1)]);
        c[now] = i;
        ans += dfs(now+1, n);

        if(now != n)
        {
            b[now+1] = 0;
        }
        else
        {
            b[1] = 0;
        }
    }
    return ans;
}

int main()
{
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a+1);
    for(int i=2; i<=n; i++)
    {
        a[i] = ((ll)a[i-1] * A + B) % 100000001;
    }
    for(int i=1; i<=n; i++)
    {
        a[i] = a[i] % C + 1;
    }
    for(int i=1; i<=n; i++)
    {
        sum *= a[i];//分母
    }
    //printf("sum == %lld\n", sum);
    ans = dfs(1, n);
    //printf("%lld", ans);
    printf("%.3lf", (double)ans/sum);

    return 0;
}

and then QVKANTIJIELE

要想做对一道题目，它前一道题目的正确选项必须和这道题目的正确选项相同，两道题目的选项组和共有a[i]*a[i-1]种，做对的情况有min(a[i], a[i-1])种，所以做对的几率为min(a[i], a[i-1]) / a[i] * a[i-1]，

化简为1 / max(a[i], a[i-1])

#include 

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e7 + 4;
const int maxm = 9e4 + 10;

int n, A, B, C, a[maxn];
double ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a+1);
    for(int i=2; i<=n; i++)
    {
        a[i] = ((ll)a[i-1] * A + B) % 100000001;
    }
    for(int i=1; i<=n; i++)
    {
        a[i] = a[i] % C + 1;
    }
    a[0] = a[n];
    //每道题做对的概率是1/max(a[i],a[i-1])
    for(int i=1; i<=n; i++)
    {
        ans += 1.0 / max(a[i-1], a[i]);
    }
    printf("%.3lf", ans);

    return 0;
}