Let's define a split of nn as a nonincreasing sequence of positive integers, the sum of which is nn.
For example, the following sequences are splits of 88: [4,4][4,4], [3,3,2][3,3,2], [2,2,1,1,1,1][2,2,1,1,1,1], [5,2,1][5,2,1].
The following sequences aren't splits of 88: [1,7][1,7], [5,4][5,4], [11,−3][11,−3], [1,1,4,1,1][1,1,4,1,1].
The weight of a split is the number of elements in the split that are equal to the first element. For example, the weight of the split [1,1,1,1,1][1,1,1,1,1] is 55, the weight of the split [5,5,3,3,3][5,5,3,3,3] is 22 and the weight of the split [9][9] equals 11.
For a given nn, find out the number of different weights of its splits.
The first line contains one integer nn (1≤n≤1091≤n≤109).
Output one integer — the answer to the problem.
7
4
8
5
9
5
In the first sample, there are following possible weights of splits of 77:
Weight 1: [77]
Weight 2: [33, 33, 1]
Weight 3: [22, 22, 22, 1]
Weight 7: [11, 11, 11, 11, 11, 11, 11]
1 #include <iostream> 2 using namespace std; 3 4 int main(){ 5 int n; 6 cin>>n; 7 n=n>>1; 8 cout<<n+1<<endl; 9 return 0; 10 }
There are n incoming messages for Vasya. The i-th message is going to be received after ti minutes. Each message has a cost, which equals to A initially. After being received, the cost of a message decreases by B each minute (it can become negative). Vasya can read any message after receiving it at any moment of time. After reading the message, Vasya's bank account receives the current cost of this message. Initially, Vasya's bank account is at 0.
Also, each minute Vasya's bank account receives C·k, where k is the amount of received but unread messages.
Vasya's messages are very important to him, and because of that he wants to have all messages read after T minutes.
Determine the maximum amount of money Vasya's bank account can hold after T minutes.
The first line contains five integers n, A, B, C and T (1 ≤ n, A, B, C, T ≤ 1000).
The second string contains n integers ti (1 ≤ ti ≤ T).
Output one integer — the answer to the problem.
4 5 5 3 5
1 5 5 4
20
5 3 1 1 3
2 2 2 1 1
15
5 5 3 4 5
1 2 3 4 5
35
In the first sample the messages must be read immediately after receiving, Vasya receives A points for each message, n·A = 20 in total.
In the second sample the messages can be read at any integer moment.
In the third sample messages must be read at the moment T. This way Vasya has 1, 2, 3, 4 and 0 unread messages at the corresponding minutes, he gets 40 points for them. When reading messages, he receives (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 = - 5 points. This is 35 in total.
1 #include <iostream> 2 using namespace std; 3 4 int n,A,B,C,T; 5 int a[1005]; 6 int main(){ 7 cin>>n>>A>>B>>C>>T; 8 for(int i=0;i<n;i++){ 9 int x; 10 cin>>x; 11 a[x]++; 12 } 13 for(int i=1;i<=T;i++) 14 a[i]+=a[i-1]; 15 if(B>=C){ 16 cout<<A*n<<endl; 17 }else{ 18 int sum = 0; 19 for(int i=T-1;i>=1;i--){ 20 sum+=a[i]; 21 } 22 sum = sum*(C-B); 23 cout<<A*n+sum<<endl; 24 } 25 26 return 0; 27 }
You are given two integers aa and bb. Moreover, you are given a sequence s0,s1,…,sns0,s1,…,sn. All values in ss are integers 11 or −1−1. It's known that sequence is kk-periodic and kk divides n+1n+1. In other words, for each k≤i≤nk≤i≤n it's satisfied that si=si−ksi=si−k.
Find out the non-negative remainder of division of n∑i=0sian−ibi∑i=0nsian−ibi by 109+9109+9.
Note that the modulo is unusual!
The first line contains four integers n,a,bn,a,b and kk (1≤n≤109,1≤a,b≤109,1≤k≤105)(1≤n≤109,1≤a,b≤109,1≤k≤105).
The second line contains a sequence of length kk consisting of characters '+' and '-'.
If the ii-th character (0-indexed) is '+', then si=1si=1, otherwise si=−1si=−1.
Note that only the first kk members of the sequence are given, the rest can be obtained using the periodicity property.
Output a single integer — value of given expression modulo 109+9109+9.
2 2 3 3
+-+
7
4 1 5 1
-
999999228
In the first example:
(n∑i=0sian−ibi)(∑i=0nsian−ibi) = 2230−2131+20322230−2131+2032 = 7
In the second example:
(n∑i=0sian−ibi)=−1450−1351−1252−1153−1054=−781≡999999228(mod109+9)(∑i=0nsian−ibi)=−1450−1351−1252−1153−1054=−781≡999999228(mod109+9).
快速幂,加逆元,再加等比数列求和。
1 #include <iostream> 2 #include <bits/stdc++.h> 3 #define ll long long int 4 #define Mod 1000000009 5 using namespace std; 6 7 ll quick(ll a,ll b){ 8 ll res = 1; 9 while(b>0){ 10 if(b&1){ 11 res=res*a%Mod; 12 } 13 b>>=1; 14 a=a*a%Mod; 15 } 16 return res%Mod; 17 } 18 19 ll n,a,b,k; 20 string s; 21 22 int main(){ 23 cin>>n>>a>>b>>k; 24 cin>>s; 25 ll ans = 0; 26 for(int i=0;i<k;i++){ 27 ll pink = s[i]=='+'?1:-1; 28 ans=(ans+pink*quick(a,n-i)*quick(b,i)%Mod+Mod)%Mod; 29 } 30 ll cnt = b*quick(a,Mod-2)%Mod;//求a的逆元 31 cnt = quick(cnt,k); 32 ll num = (n+1)/k; 33 ll sum; 34 if(cnt == 1){ 35 sum = num*ans%Mod; 36 }else{ 37 sum = (ans*(quick(cnt,num)-1)%Mod*quick(cnt-1,Mod-2)+Mod)%Mod; 38 } 39 cout<<sum<<endl; 40 return 0; 41 }