2020安徽省省賽
D. 字串修改
對于兩個由 0 與 1 組成的長度均為 N 的序列 S 和 T，f（S,T）定義如下：
重復如下操作，使得序列 S 與序列 T 相同。f（S,T）是經過操作后，所需要的最少的花
費。
改變 S[i]的值（0 改為 1 或者 1 改為 0），它的花費為 D*C[i]，其中 D 是在此操作之前，
序列中滿足 S[j]≠T[j]的 j 的個數（1<=j<=N）。C[i]表示對 i 位置進行變換的代價。
對于一個固定長度 N，共有2? ? (2? ? 1)對由 01 組成的序列（S,T），計算所有 f(S,T)
的總和，并輸出它對10? + 7的結果。
資料范圍
1 ≤ ? ≤ 2 ? 10?
1≤???? ≤ 10?
輸入說明
輸入第一行為一個整數 N，表示 S與 T的長度，第二行共 N個整數，C[1],C[2],C[3],…,C[N]。
輸出說明
輸出一個整數，所有 f(S,T)之和對10? + 7取模的結果。
樣例一
輸入樣例
1
1000000000
輸出樣例
999999993
樣例二
輸入樣例
2
5 8
輸出樣例
124
提示
對樣例 1，S 可取 0、1，T 可取 0、1，共有 f(0,0)，f(0,1)，f(1,0)，f(1,1)四種情況
f(0,0)=0,f(1,1)=0,f(1,0)=f(0,1)=10^9，故最終結果為 2*10^9, 取模可得 999999993。
樣例 2 中，針對 S=(0,1),T=(1,0)這個序列對，首先將 S1 改為 1，造成的花費為 5*2=10，
因為 S1 與 T1，S2 與 T2 均不相同。再將 S2 改為 0，造成的花費為 8*1=8，故 f(S,T)=18。
解法：運用數學方法
通過一些數學方法對題目要求進行求解，首先求逆元是為了算組合Cn,m。通過快速冪的方法計算2的n次方。然后通過數學的方法，從第一位開始，有四種狀態，兩種相等兩種不等，當狀態不等的時候開始計算花費，后面n-1個數，人選m個不等，即為Cn-1,m，共兩種狀態，即2^m。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL maxn(200005), mod(1e9 + 7);
LL Jc[maxn];
void calJc() //求maxn以內的數的階乘
{
Jc[0] = Jc[1] = 1;
for(LL i = 2; i < maxn; i++)
Jc[i] = Jc[i - 1] * i % mod;
}
//費馬小定理求逆元
LL pow(LL a, LL n, LL p) //快速冪 a^n % p
{
LL ans = 1;
while(n)
{
if(n & 1) ans = ans * a % p;
a = a * a % p;
n >>= 1;
}
return ans;
}
LL niYuan(LL a, LL b) //費馬小定理求逆元
{
return pow(a, b - 2, b);
}
LL C(LL a, LL b) //計算C(a, b)
{
if(a < b) return 0;
return Jc[a] * niYuan(Jc[b], mod) % mod
* niYuan(Jc[a - b], mod) % mod;
}
//快速冪
LL poww(int a,int b){
LL ans=1,base=a;
while(b!=0){
if(b&1!=0)
ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
LL d[maxn]; //存放D資料
LL a[maxn]; //存放需要乘以多少次D[i]
int main()
{
calJc();//初始化
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]=a[i]*a3%mod;
}
LL ans=0;
for(int i=1;i<=n;i++)
{
ans=ans+a[i]*d[i]%mod;
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/241126.html
標籤：C++ 語言
上一篇：C++
下一篇：關于485輪詢邏輯問題