首页 > 代码库 > URAL 1528 Sequence
URAL 1528 Sequence
SequenceCrawling in process... Crawling failed Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
You are given a recurrent formula for a sequence
f:
f(n) = 1 + f(1)g(1) +
f(2)g(2) + … + f(n?1)g(n?1),
where g is also a recurrent sequence given by formula
g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + … + 2g(n?1) ?
g(n?1)g(n?1).
It is known that f(1) = 1, g(1) = 1. Your task is to find
f(n) mod p.
Input
The input consists of several cases. Each case contains two numbers on a single line. These numbers are
n (1 ≤ n ≤ 10000) and p (2 ≤ p ≤ 2·109). The input is terminated by the case with
n = p = 0 which should not be processed. The number of cases in the input does not exceed 5000.
Output
Output for each case the answer to the task on a separate line.
Sample Input
| input | output |
|---|---|
1 2 2 11 0 0 |
1 2 |
题意：如题。
思路：哇。
一開始看错题啦。
不难发现f（n）的通项啦。
AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stdlib.h>
using namespace std;
int main(){
int n,p;
while(~scanf("%d%d",&n,&p)){
if(n==0&&p==0) break;
long long ans=1;
for(int i=2;i<=n;i++){
ans*=i%p;
ans%=p;
}
printf("%d\n",ans%p);
}
return 0;
}
??
URAL 1528 Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。