Ask this kind of method how to get the biggest f (S, T)?-CodePudding

2020 in anhui province
D. string change
For the length of the two is composed of 0 S and 1 S are the sequence of N S and T, f (S, T) are defined as follows:
Repeat the following operation, making the sequence S the same as the sequence T, f (S, T) after operation, need at least spend
Fee,
Change S [I] value (0 or 1 to 0), its cost is D * C [I], where D is the before the operation,
Sequence of meet S [j] indicates T [j] j number (1 & lt;=jFor a fixed length N, a total of 2? ? (2? ? 1) for the sequences of 01 (S, T), and calculate all f (S, T)
The sum of, and output it to the 10? The result of + 7,
Data range
1 or less? 2 or less? 10?
1 or less?????? 10 or less?
The input description
Input the first conduct an integer N, S and T, the length of the second line, a total of N integers, C [1], C [2], [3], C... , C [N],
The output shows that
Output an integer, the sum of all f (S, T) of 10? + 7 modulus results,
Sample a
The input sample
1
1000000000
The output sample
999999993
The sample 2
The input sample
2
5 8
The output sample
124
Tip
To sample 1, S advisable to 0, 1, T desirable 0, 1, a total of f (0, 0) and f (0, 1), f (1, 0) and f (1, 1) four
=0 f (0, 0) and f (1, 1)=0, f (1, 0)=f (0, 1)=10 ^ 9, so the final result for 2 * 10 ^ 9, modulus can get 999999993,
Sample 2, in view of the S=(0, 1), T=(1, 0) for this sequence, first change the S1 to 1, the cost is 5 * 2=10,
Because S1 and T1, S2 and T2 are not the same, and then change the S2 to 0, the cost for 8 * 1=8, therefore, f (S, T)=18,

Method: using mathematical method
The topic request is solved by some mathematical methods, inverse element is first to calculate combination Cn, m, calculated by the method of fast power exponent n 2, and then, by using the method of mathematics from the first beginning, there are four state, two equal, when the state began to calculate cost, the number of n - 1, candidate ranged from m, m, is the Cn - 1, a total of two states, namely 2 ^ m,

 # include 
#include 
#include 
using namespace std; 

Typedef long long LL; 
Const LL maxn (200005), the mod e9 + 7 (1); 
LL Jc [maxn]; 

Within the void calJc maxn ()//o number of factorial 
{
Jc [0]=Jc [1]=1; 
For (LL I=2; i Jc [I]=Jc [I - 1] * I % mod; 
} 

//inverse fermat's little theorem 
LL pow (LL a, LL n, LL p)//fast power a ^ n % p 
{
LL ans=1; 
While (n) 
{
If (n & amp; 1) ans=ans * a % p; 
A=a * a % p; 
N & gt;>=1; 
} 
Return ans. 
} 

LL niYuan (LL a, LL b)//inverse fermat's little theorem 
{
Return pow (- 2 a, b, b); 
} 

LL (LL a, LL b/C/calculate C (a, b) 
{
If (a & lt; B) return 0; 
Return Jc [a] * niYuan (Jc [b], mod) % mod 
* niYuan (Jc/a - b, mod) % mod; 
} 


//fast power 
LL poww (int a, int b) {
LL ans=1, base=a; 
While (b!=0) {
If (b& 1!=0) 
Ans=ans * base % mod; 
The base=base * base % mod; 
b>=1; 
} 
Return ans. 
} 

LL d [maxn];//store D data 
LL a [maxn]; Deposit//how many times need to multiply D [I] 

Int main () 
{
CalJc ();//initialize 
int n; 
cin> n; 
for(int i=1; i<=n; I++) 
{
cin> D [I]; 
} 

for(int i=1; i<=n; I++) 
{
LL a1, a2, a3=0; 
A1=poww (4, I - 1); 
A2=poww (2, n - I + 1); 
A [I]=a1 * a2 % mod; 
for(int k=0; K<=n - (I); K++) 
{
A3=a3 + C (n - I, k) * (k + 1) % mod; 
A3=a3 % mod; 
} 
A [I]=[I] a * a3 % mod; 
} 

LL ans=0; 
for(int i=1; i<=n; I++) 
{
Ans=ans + a * d [I] [I] % mod; 
} 
coutreturn 0; 
}