程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5288OO’s Sequence

hdu5288OO’s Sequence

編輯:C++入門知識

hdu5288OO’s Sequence


//給一個序列
//定義函數f(l ,r) 為區間[l ,r] 中
//的數ai不是在這個區間其他任意數aj的倍數
//求所有f(l,r)之和
//對於每一個數a[i]找其最左的區間l[i]和最右的區間r[i]
//包含a[i]且使得a[i]滿足條件的個數為(i-l[i]+1)*(r[i] - i + 1)
//對於每一個r[i]只要從左到右遍歷
//pre[i] 表示i最後出現的位置
//對於一個數a[i],枚舉其所有倍數值
//在其左邊找到其對應的位置,那麼 r[pre[j]] = i - 1;
//同理可以得到l[i]
#include
#include
#include
using namespace std ;
const int maxn = 100010 ;
const int mod = 1e9+7 ;
int a[maxn];
typedef __int64 ll ;
ll last[maxn] ;
ll pre[maxn] ;
ll l[maxn] ;
ll r[maxn] ;
int main()
{
//freopen(in.txt ,r ,stdin) ;
int n ;
while(~scanf(%d ,&n))
{
memset(last , 0 ,sizeof(last)) ;
memset(pre , 0 ,sizeof(pre)) ;
for(ll i =1;i <= n;i++)
{
l[i] = 1;r[i] = n ;
scanf(%d ,&a[i]) ;
for(ll j = a[i] ;j < maxn/10;j+=a[i])
if(pre[j] != 0 && r[pre[j]] == n)
r[pre[j]] = i - 1;
pre[a[i]] = i;
}
for(ll i = n ;i >= 1;i--)
{
for(ll j = a[i];j < maxn/10;j+=a[i])
if(last[j] != 0 && l[last[j]] == 1)
l[last[j]] = i + 1;
last[a[i]] = i ;
}
ll ans = 0 ;
for(ll i = 1;i <= n;i++)
ans = (ans + (((i-l[i]+1)%mod)*((r[i] - i + 1)%mod))%mod)%mod ;
printf(%I64d ,ans) ;
}
return 0 ;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved