注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

BestCoder Round #8  

2014-09-08 14:43:46|  分类: BestCoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1001 Summary (HDU 4989)

给你N个数,他们两两的和可以组合出N*(N-1)/2个数,将这些数去重,求剩下的所有数的和。
2≤N≤100,-1e9≤每个数≤1e9。
Solution
直接做就行了,记得结果开long long存。
int a[100086];
std::vector<int> b;

int main(){
int n;
while(scanf("%d", &n) != EOF){
b.clear();
f(i, 1, n) scanf("%d", a + i);
f(i, 1, n) f(j, i + 1, n) b.push_back(a[i] + a[j]);
std::sort(b.begin(), b.end());
b.erase(std::unique(b.begin(), b.end()), b.end());
LL sum = 0;
foreach(i, b) sum += (LL) *i;
std::cout << sum << std::endl;
}
return 0;
}
1002 Reading Comprehension (HDU 4990)
题目里给出了一个暴力程序,让你实现这个算法。程序如下:

读入n和m;

ans=0;

for i从1循环到n{

如果i是奇数 ans=(ans*2+1)%m;

否则 ans=ans*2%m;

}

输出ans;

1≤n,m≤1e9。
Solution
把n是奇数的情况写出来,大概是1,5,21,85,……a[i+1]=4a[i]+1。
n是偶数:2,10,42,……a[i+1]=4a[i]+2。分别矩阵快速幂搞一搞就行了。

另一种做法:考虑n是奇数,那么把它写成二进制大概是010101…01的形式,把它乘3就是111111…11,可以直接算出(2^n-1)/3%m。(注意中间要对3m取模)如果n是偶数就算出前一个答案乘2就行了。

场上cha了3个人,都是这道题n=m=1的时候输出了1……
关于这个数列的更多信息见:http://oeis.org/A000975
LL MOD;
struct mat{
    LL a, b;
    inline mat(LL _a = 0, LL _b = 0) :a(_a % MOD), b(_b % MOD){}
};
inline mat operator *(const mat x, const mat y){
    return mat(x.a * y.a, x.b * y.a + y.b);
}
inline mat pow(const mat x, int y){
    mat ans(1, 0);
    h(i, 30, 0){
        ans = ans * ans;
        if(y & (1 << i)) ans = ans * x;
    }
    return ans;
}

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
        MOD = m;
        if(n % 2){
            mat ans = pow(mat(4, 1), n / 2);
            int aa = (ans.a + ans.b) % MOD;
            printf("%d\n", aa);
        }else{
            mat ans = pow(mat(4, 2), n / 2);
            int aa = ans.b;
            printf("%d\n", aa);
        }
    }
    return 0;
}
1003 Ordered Subsequence (HDU 4991)
给出一个长度为n的序列,求它长度为m的上升子序列的个数mod 123456789。
n≤10000,m≤100,0≤每个数≤987654321。
Solution
设f[i][j]表示以第i位结尾的长度为j的上升子序列的个数,那么f[i][j]=sigma_{k}f[k][j-1],其中k满足k<i且a[k]<a[i]。只需要把所有数排序从小到大从后往前处理,用树状数组优化即可。
#define MOD 123456789
int n, m, a[10086], pos[10086];
int tt[108][10086];
inline void chg(int *tree, int x, int y){
    for(; x <= n; x += x & -x) tree[x] = (tree[x] + y) % MOD;
}
inline int sum(int *tree, int x){
    int ans = 0;
    for(; x; x -= x & -x) ans = (ans + tree[x]) % MOD;
    return ans;
}
inline bool less(int x, int y){
    return a[x] < a[y] || (a[x] == a[y] && x > y);
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        f(i, 1, n) scanf("%d", a + i);
        f(i, 1, n) pos[i] = i;
        std::sort(pos + 1, pos + n + 1, less);
        memset(tt, 0, sizeof(tt));
        f(ii, 1, n){
            int i = pos[ii];
            chg(tt[1], i, 1);
            f(j, 2, m) chg(tt[j], i, sum(tt[j - 1], i - 1));
        }
        printf("%d\n", sum(tt[m], n));
    }
    return 0;
}
1004 Primitive Roots (HDU 4992)
给出n,求模n的所有原根。
n≤10^6,数据大概200组(当然不都是最大的),时限2s。
Solution
题解说道,先暴力找出一个原根g,然后利用“g^d是模m的原根,当且仅当gcd(d,phi(m))=1”找其余的……
需要加FastIO之类的……
inline int gcd(int x, int y){
while
(y){
int
t = x % y; x = y; y = t;
}

return
x;
}


LL MOD;
inline
int pow(int x, int y){
LL ans = 1;
h(i, 30, 0){
ans = ans * ans % MOD;
if
(y & (1 << i)) ans = ans * (LL) x % MOD;
}

return
(int) ans;
}


std::vector<int> phidiv;
inline
void getdiv(int n){
phidiv.clear();
for
(int i = 2; i * i <= n; ++i) if(n % i == 0){
phidiv.push_back(i);
while
(n % i == 0) n /= i;
}

if
(n > 1) phidiv.push_back(n);
}


int
phi;
inline
void getphi(int n){
phi = 1;
for
(int i = 2; i * i <= n; ++i) if(n % i == 0){
phi *= (i - 1); n /= i;
while
(n % i == 0){
phi *= i; n /= i;
}
}

if
(n > 1) phi *= (n - 1);
}

bool
av[1000086];
int
main(){
int
n;
while
(scanf("%d", &n) != EOF){
// f(n, 1, 1000){
memset(av, 0, sizeof(av));
getphi(n); getdiv(phi);
MOD = n;
int
G = -1;
f(i, 1, n){
if
(gcd(i, n) == 1){
bool
can = true;
foreach(j, phidiv) if(pow(i, phi/ *j) == 1){
can = false; break;
}

if
(can){
G = i; break;
}
}

if
(i > 10000 && G == -1) break;
}

if
(G == -1) printf("-1"); else{
av[G] = 1;
g(i, 2, phi) if(gcd(i, phi) == 1) av[pow(G, i)] = 1;
}

bool
flag = true;
g(i, 0, n) if(av[i]){
if
(flag){
write(i); flag = false;
}
else{
putchar(' '); write(i);
}
}

printf("\n");
}

return
0;
}

  评论这张
 
阅读(55)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018