首页 > ACM题库 > HDU-杭电 > HDU 4475-Downward paths-数论-[解题报告]HOJ
2015
07-16

HDU 4475-Downward paths-数论-[解题报告]HOJ

Downward paths

问题描述 :

================
  Hi! I am an ACMer from CSU. This contest made by me is to celebrate my girlfriend’s birthday although the problems in this contest do not relate to her in fact. :) Any way, happy birthday to you, honey!
  Thanks to LCY, I have this chance to share my ideas and works with you. Good luck and have fun!
================
  We have a graph with size = N like that in Figure 1. Then we are going to find a downward path from the top node to one bottom node.
  First, we select the top node as the beginning. Then at any node, we can go horizontally or downward along the blue edge and reach the next node. The finding will be end when we reach one of the bottom nodes. After that we can get a downward path from the top node to one bottom node. Note that we can not pass a blue edge that we have passed ago during each finding.
  Your task is to calculate there exists how many downward paths.
Yet Another Multiple Problem

输入:

  There is an integer T (1 <= T <= 1000) in the first line, which indicates there are T test cases in total.
  For each test case, there is only one integer N (1 <= N <= 10^18) indicates the size of the graph.

输出:

  There is an integer T (1 <= T <= 1000) in the first line, which indicates there are T test cases in total.
  For each test case, there is only one integer N (1 <= N <= 10^18) indicates the size of the graph.

样例输入:

2
1
2

样例输出:

2
8
Hint
  For Sample 2, the yellow paths in Figure 2 show the 8 downward paths.
Yet Another Multiple Problem

题目:Downward paths

 

设size=i,答案是ai;

       a1=2=1+1;

       a2=8=2+2*2+2;

       a3=48=8+8*2+8*2+8;

       a4=384 =48+48*2+48*2+48*2+48;

       ……

很明显规律:an=an-1+2*(n-1)an-1+an-1=2*n*an-1;  即:an=2^n*n!

#include <iostream>

using namespace std;
typedef unsigned long long LL;

const LL MOD = 1000003;
LL arr[1000100];

int main()
{
    LL t,n,i;
    arr[0]=0;arr[1]=2;
    for(i=2;i<=MOD;i++)
        arr[i]=(arr[i-1]*2*i)%MOD;
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n>=MOD)
        {
            cout<<"0"<<endl;
            continue;
        }
        cout<<arr[n]<<endl;
    }
    return 0;
}

 

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/8888072