2015年3月28日 星期六

2015/03/28 HSNU OJ Problem : 53 - 買醬油II

// http://hoj.twbbs.org/judge/problem/view/53
#include <iostream>
#include <cstdio>

using namespace std;

#define MOD 910193

int Ans[20000];
int mem[2][20000];

int *DP1, *DP2;

int main()
{
    mem[0][0] = Ans[0] = 1;
    DP1 = mem[0];

    for(int i = 1; i <= 10000; i++)
    {
        DP2 = mem[i%2];

        for(int j = 0; j <= i; j++)
        {
            DP2[j] = 0;

            DP2[j] += DP1[j];
            if(j) DP2[j] += DP2[j-1];

            DP2[j] %= MOD;
        }

        Ans[i] = DP2[i];
        DP1 = DP2;
    }

    int N;
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", Ans[x]);
    }
}

沒有留言:

張貼留言