题解 - Vijos

0

aciffar LV 10 @ 2016-11-04 13:40:31

醉了...为什么减法mod没+大质数是MLE
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 158840 KiB, score = 9
测试数据 #1: Accepted, time = 0 ms, mem = 158840 KiB, score = 9
测试数据 #2: Accepted, time = 250 ms, mem = 158844 KiB, score = 9
测试数据 #3: Accepted, time = 328 ms, mem = 158844 KiB, score = 9
测试数据 #4: Accepted, time = 0 ms, mem = 158840 KiB, score = 9
测试数据 #5: Accepted, time = 0 ms, mem = 158840 KiB, score = 9
测试数据 #6: Accepted, time = 125 ms, mem = 158844 KiB, score = 9
测试数据 #7: Accepted, time = 15 ms, mem = 158840 KiB, score = 9
测试数据 #8: Accepted, time = 31 ms, mem = 158844 KiB, score = 9
测试数据 #9: Accepted, time = 140 ms, mem = 158840 KiB, score = 9
测试数据 #10: Accepted, time = 0 ms, mem = 158840 KiB, score = 10
Accepted, time = 904 ms, mem = 158844 KiB, score = 100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define _m 1000000007
using namespace std;

LL n, m, p;
LL d[1010][10010], s[1010][10010];

LL powmod(LL x) {
if(!x) return 1;
if(x == 1) return 2;
LL a = powmod(x>>1);
return (x&1) ? a*a*2%_m : a*a%_m;
}

int main() {
cin >> n >> m;
int i, j;
d[1][0] = 1;
for(i = 0;i <= m;i ++) s[1][i] = 1;
for(i = 2;i <= n;i ++) {
for(j = 0;j <= m;j ++) {
if(j >= i) d[i][j] = (s[i-1][j] - s[i-1][j-i] + _m) % _m; else d[i][j] = s[i-1][j];
if(j) s[i][j] = (s[i][j-1] + d[i][j]) % _m; else s[i][j] = d[i][j];
}
}
cout << powmod(d[n][m]);
return 0;
}

0

xiaochua LV 8 @ 2013-10-08 20:26:11

测试数据 #0: Accepted, time = 0 ms, mem = 2128 KiB, score = 9
测试数据 #1: Accepted, time = 0 ms, mem = 2132 KiB, score = 9
测试数据 #2: Accepted, time = 187 ms, mem = 2120 KiB, score = 9
测试数据 #3: Accepted, time = 218 ms, mem = 2128 KiB, score = 9
测试数据 #4: Accepted, time = 0 ms, mem = 2128 KiB, score = 9
测试数据 #5: Accepted, time = 0 ms, mem = 2124 KiB, score = 9
测试数据 #6: Accepted, time = 93 ms, mem = 2128 KiB, score = 9
测试数据 #7: Accepted, time = 0 ms, mem = 2128 KiB, score = 9
测试数据 #8: Accepted, time = 15 ms, mem = 2132 KiB, score = 9
测试数据 #9: Accepted, time = 109 ms, mem = 2124 KiB, score = 9
测试数据 #10: Accepted, time = 15 ms, mem = 2128 KiB, score = 10

Accepted, time = 637 ms, mem = 2132 KiB, score = 100；

疑问：
令t=大神排列数。
根据费马小定理，应该令t%=1000000006;cout<<2^t%1000000007;
但是只能过3组，而令t对1000000007取余却AC了。

0

darin LV 10 @ 2009-10-13 21:08:57

vag 6k

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 789ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行超时...

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：73 有效耗时：789ms

puppy

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 244ms

├ 测试数据 04：答案正确... 306ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

├ 测试数据 11：答案正确... 0ms

为什么同是评测机，，差距就这么大呢。！！

0

Matt LV 10 @ 2009-10-01 14:36:27

耍了一把小聪明

结果很无语

0

ahcy1994 LV 8 @ 2009-09-19 22:03:49

谢了prince_hao的提醒

0

lostoy LV 6 @ 2009-09-13 17:50:09

这个题虽然ac了,但是如果直接用f [ j ] = f [ j-1 ] + ff [ j ] - ff [ j-i ] mod bigprime 这个递推,最后输出2^ans mod bigprime的结果,和原问题还等价么?

0

kdefgey LV 8 @ 2009-09-12 23:19:13

一开始没用快速幂，结果28分，3-9都超时

0

宇智波带屌 LV 9 @ 2009-09-12 20:00:03

终于过了，多谢prince_hao大牛提醒

0

wsdhhh LV 8 @ 2009-09-11 16:18:04

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 119ms

├ 测试数据 04：答案正确... 181ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

├ 测试数据 11：答案正确... 0ms

0

prince_hao LV 10 @ 2009-09-06 17:17:12

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 228ms

├ 测试数据 04：答案正确... 306ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 119ms

├ 测试数据 11：答案正确... 0ms

第五个点和第十个点错误输出1的注意减法MOD时+1000000007

0

mike_nzk LV 10 @ 2009-09-04 22:25:56

沙茶题。。。

注意当j

0

玛维-影之歌 LV 10 @ 2009-09-04 08:50:17

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 72ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：184ms

用int64......好囧的时间

0

ufo172849z LV 10 @ 2009-09-03 15:54:05

f表示i个数的排列中有j个逆序对的排列个数

有递推式

f=f+....+f

然后递推式的优化楼下寒蝉已经讲的很清楚了。

实现的时候用滚动数组就可以了。

但是写的时候要切记用int64，虽然好像1000000007*2小于longint但是我也不知道为什么。改了就过了。

0

小岛 LV 10 @ 2009-09-03 12:55:35

这个恩..spoj也有一题..不过数据范围小的多..

Link:

https://www.spoj.pl/problems/PERMUT1/

0

zgx LV 10 @ 2009-09-03 09:20:22

三位神牛分别是：

tyt、pzy、njn

0

dragon007 LV 10 @ 2009-09-02 11:54:20

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 72ms

├ 测试数据 04：答案正确... 119ms

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：82 有效耗时：191ms

出现这样结果的人注意一个很小的错误

i

0

飘の★ LV 10 @ 2009-09-01 22:27:39

第一个点神奇的200号错误了= =

最后发现

第一个点是2^0也就是1。。。。

0

寒蝉 LV 9 @ 2009-09-01 11:40:32

基本递推式:

f [ i ][ j ] = f[i][j]+f[k] ( (j-i+1)

0

hxbks2ks LV 10 @ 2009-08-30 20:55:06

递推+麦森数的方法

0

luyifan LV 10 @ 2009-08-30 18:43:00

考试没用int64,滚动数组

题解

26 条题解

Accepted, time = 637 ms, mem = 2132 KiB, score = 100；

膜拜

信息

状态

开发

支持

题解

26 条题解

Accepted, time = 637 ms, mem = 2132 KiB, score = 100；

膜拜

信息

状态

开发

支持

还没有账户？

登录