题目 题目描述

小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并 观察细胞分裂的规律。

他选取了一种特别的细胞，每天每个该细胞可以分裂出 x − 1 个新的细胞。

小 X 决定第 i 天向培养皿中加入 i 个细胞（在实验开始前培养皿中无细胞）。

现在他想知道第 n 天培养皿中总共会有多少个细胞。

由于细胞总数可能很多，你只要告诉他总数对 w 取模的值即可。

输入格式

第一行三个正整数 n, x, w。

输出格式

一行一个数表示第 n 天的细胞总数对 w 取模的值。

样例输入

2 2 47

样例输出

4

数据范围

对于 100% 的数据，n ≤ 107，1 ≤ x, w ≤ 231 − 1。

对于其中 30% 的数据，x = 1。

#include<bits/stdc++.h>
using namespace std;
long long ans[10000005];
int main(){
	int n,x,w;
	cin>>n>>x>>w;
	ans[1]=1;
	for(int i=2;i<=n;i++){
		ans[i]=(i+ans[i-1]*x)%w;
	}
	cout<<ans[n];
    return 0;
}