TopCoder SRM 565



Problem Statement:  
Manao is traversing a valley inhabited by monsters. During his journey, he will encounter several monsters one by one. The scariness of each monster is a positive integer. Some monsters may be scarier than others. The i-th (0-based index) monster Manao will meet has scariness equal to dread[i].  Manao is not going to fight the monsters. Instead, he will bribe some of them and make them join him. To bribe the i-th monster, Manao needs price[i] gold coins. The monsters are not too greedy, therefore each value in price will be either 1 or 2.  At the beginning, Manao travels alone. Each time he meets a monster, he first has the option to bribe it, and then the monster may decide to attack him. A monster will attack Manao if and only if he did not bribe it and its scariness is strictly greater than the total scariness of all monsters in Manao's party. In other words, whenever Manao encounters a monster that would attack him, he has to bribe it. If he encounters a monster that would not attack him, he may either bribe it, or simply walk past the monster
You are given the vector <int>s dread and price. Compute the minimum price Manao will pay to safely pass the valley.
dp[n][p]=max{dp[n-1][p](dp[n-1][p]>scariness[n]), dp[n-1][p-price[n]]+scariness[n]}
using namespace std;
class MonstersValley2{
	int minimumPrice(vector <int> dread,vector <int> price){
		long long dp[21][41];
		for(int i=0;i<=40;i++)dp[0][i]=0;
		for(int i=1;i<=dread.size();i++){
			for(int j=0;j<=40;j++){
					long long t=dp[i-1][j-price[i-1]]+dread[i-1];
				cout<<dp[i][j]<<' ';
		for(int j=0;j<=40;j++){
			if(dp[dread.size()][j]!=-1)return j;
		return -1;


Problem Statement:
A divisible sequence with starting value N and length H is a sequence of positive integers with the following properties:
The sequence has H elements, labeled A[0] through A[H-1].
A[0] equals N.
For each i between 0 and H-2, inclusive, A[i+1] divides A[i].
You are given the ints N and H. Let C be the count of all divisible sequences with starting value N and length H. Return the value (C modulo 1,000,000,009).
这样一步步生成下一个元素的过程中,只要各个因子对应的指数不增,则最终形成一个Divisible Sequence。


如x=2,H=3的情况下,操作序列:减1、取数、减1、取数、取数 形成一个单调不增序列1,0,0


    // Let us use trial divison to find prime factors p
    for (int p=2; p <= N/p; p++) {
        int c = 0;
        while (N % p == 0) {
            N /= p;	
        res = ( res * C(H-1+c, c) ) % MOD;
    if (N > 1) {
        // N is one last prime factor, c = 1
        // C(H-1+1,1) = H
        res = ( res * H ) % MOD;




final int MOD = 1000000009;
// Calculates x raised to the y-th power modulo MOD
long modPow(long x, long y)
    long r=1, a=x;
    while (y > 0) {
        if ( (y&1)==1 ) {
            r = (r * a) % MOD;
        a = (a * a) % MOD;
        y /= 2;
    return r;
// Modular multiplicative inverse through Fermat's little theorem:
long modInverse(long x)
    return modPow(x, MOD-2);
// Modular division x / y, find modular multiplicative inverse of y
// and multiply by x.
long modDivision(long p, long q)
    return (p * modInverse(q)) % MOD;
// Binomial coifficient C(n,k) in O(k) time.
long C(long n, int k)
    if (k > n) {
        return 0;
    long p = 1, q = 1;
    for (int i=1; i<=k; i++) {
        q = ( q * i) % MOD;
        p = ( p * (n - i + 1) ) % MOD;
    return modDivision( p, q);

这里出现了modular divisionModular multiplicative inverse(模反元素)的概念 和 费马小定理(Fermat's little theorem)

如果a-1和x对于m是同模的,则x就是a的模反元素,这时有a*x mod m = a*a-1 mod m = 1

模反元素可以用于计算modular division,p/q mod m 可以表示为 p*q-1 mod m,其中q-1是q的模反元素。


假如a是一个整数,p是一个质数,这个定理表明amod p = a mod p

如果a不是p的倍数,这个定理可以写成ap-1mod p = 1。


怎样计算xy :



这是因为xy=(x2)y/2*xy%2 ,这样计算xy就转化为计算(x2)y/2

Category: TopCoder | Tags: TopCoder 数论 费马小定理 | Read Count: 2387
Aiden Pearce Coat 说:
2019年10月08日 12:44

Stunning, brilliant site design! To what extent have you been blogging for? you made blogging look simple. The general look of your site is magnificent, and additionally the substance!. Much obliged For Your work.

windows 10 image dow 说:
2020年2月01日 13:11

Visit here to know the complete information of windows 10 operating system.

roblox hack apk 说:
2020年4月05日 13:15

All you need to earn more and more robux as much as you can.

essayhave review 说:
2020年5月02日 21:15

Awesome! you have explained the divisible sequence in such a great way. Thanks for this help here I have one question that can you compute the price for me so that I can pass the valley safely. Much obliged for your assistance.

seo service london 说:
2024年1月16日 07:33

This is a great feature for sharing this informative message. I am impressed by the knowledge you have on this blog. It helps me in many ways. Thanks for posting this again

seo service london 说:
2024年1月16日 07:34

This is a great feature for sharing this informative message. I am impressed by the knowledge you have on this blog. It helps me in many ways. Thanks for posting this again

seo service UK 说:
2024年2月22日 13:42

Marketing1on1 is surely an website marketing company which will help webmasters to control their online promoting campaigns

登录 *

loading captcha image...
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com