[第一波模拟\day2\T1] {病毒分裂}(split.cpp)

【题目描述】

A 学校的实验室新研制出了一种十分厉害的病毒。由于这种病毒太难以人工制造
了，所以专家们在一开始只做出了一个这样的病毒。
这个病毒被植入了特殊的微型芯片，使其可以具有一些可编程的特殊性能。最重
要的一个性能就是，专家们可以自行设定病毒的分裂能力K，假如现在有x 个病
毒，下一个分裂周期将会有Kx 个一模一样的病毒。你作为该实验室的数据分析
员，需要统计出在分裂到第N 个周期前，一共有多少个病毒单体进行了分裂。一
开始时总是只有一个病毒，这个局面算作第一个周期。由于答案可能很大，专家
们只需要你告诉他们对给定的P 取模后的答案。

【输入】

一行三个整数，依次是K, N, P。

【输出】

一行一个整数，你的答案（对P 取模）。
输入样例一

样例一解释：第一个周期有1 个病毒，产生了一次分裂。第二个周期有1*5=5
个病毒，这五个病毒都会分裂。所以第三个周期前一共进行了1+5 等于6 次分裂。
答案即为6 mod 7 = 6。
输入样例二

【数据范围及提示】

测试点编号备注范围
1 ~ 5
P 是质数
1 < K, N, P < 10000
6 ~ 7 1 < N < 10^18
8 ~ 10 P不是质数1 < K , P < 2^31

【解法】

80分，乱搞+利用数据

我们知道这明显是等比数列求和，用公式直接搞，此外利用7（实际上能过8个）个数据点的p是质数的性质快速求逆元

#include <stdio.h>

#include <string.h>

#define maxbuff 1<<20

#define ll long long

#define set_file(File) freopen(File".in", "r", stdin), freopen(File".out", "w", stdout)

#define close_file() fclose(stdin), fclose(stdout)

char buff[maxbuff], *iter = buff;

template<class Type> inline void read(register Type &x)

	{

	x = 0;

	while(*iter < '0' || *iter > '9') ++iter;

	while(*iter >= '0' && *iter <= '9') x = x * 10 + *iter++ - '0';

	}

ll k, n, mo, ans;

ll inv(ll n, ll p)

	{

	ll ret = 1;

	for(ll i = p; i; i >>= 1, n = (n * n) % mo)

		if(i & 1) ret = (ret * n) % mo;

	return ret;

	}

ll pow(ll n, ll t)

	{

	ll ret = 1;

	for(; t; t >>= 1, n = (n * n) % mo)

		if(t & 1) ret = (ret * n) % mo;

	return ret;

	}

int main()

	{

	set_file("split");

	fread(buff, 1, maxbuff, stdin);

	read(k), read(n), read(mo);

	ans = pow(k, n - 1) - 1;

	if(ans < 0) ans += mo;

	ans = (ans * inv(k - 1, mo - 2)) % mo;

	printf("%I64d\n", ans);

	close_file();

	return 0;

	}

100分，一种不是很协调的方法。直接考虑保留分母的因子，也就是将mod数乘上个分母，之后加个快速乘加速

#include <stdio.h>

#include <string.h>

#define maxbuff 1<<20

#define ll long long

#define set_file(File) freopen(File".in", "r", stdin), freopen(File".out", "w", stdout)

#define close_file() fclose(stdin), fclose(stdout)

char buff[maxbuff], *iter = buff;

template<class Type> inline void read(register Type &x)

	{

	x = 0;

	while(*iter < '0' || *iter > '9') ++iter;

	while(*iter >= '0' && *iter <= '9') x = x * 10 + *iter++ - '0';

	}

ll k, n, mo, ans, P;

ll mul(ll x, ll y)

	{

	ll ret = 0;

	for(; y; y >>= 1, x = (x + x) % P)

		if(y & 1) ret = (ret + x) % P;

	return ret;

	}

ll pow(ll n, ll t)

	{

	ll ret = 1;

	for(; t; t >>= 1, n = mul(n, n))

		if(t & 1) ret = mul(ret, n);

	return ret;

	}

int main()

	{

	set_file("split");

	fread(buff, 1, maxbuff, stdin);

	read(k), read(n), read(mo);

	P = (k - 1) * mo;

	ans = ((pow(k, n - 1) - 1 + P) % P/ (k - 1)) % mo;

	printf("%I64d\n", ans);

	close_file();

	return 0;

	}

巴特西