11155  Be Efficient
Moderator: Board moderators
11155  Be Efficient
Can anyone tell me whats the idea of this problem
cause i am getting TLE
thanks
cause i am getting TLE
thanks

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Getting WA..
Is sum 0 considered as Multiple of M?
What would be the result for sequence
with M = 2.
With considering sum 0 as Multiple of M, it will be 6.
Without considering sum 0 as Multiple of M, it sould be 3.
Which is right ? (maybe both wrong...)
Is sum 0 considered as Multiple of M?
What would be the result for sequence
Code: Select all
1 0 1 0 0
With considering sum 0 as Multiple of M, it will be 6.
Code: Select all
({1,0,1}, {0}, {1,0,1,0}, {1,0,1,0,0}, {0,0}, {0})
Code: Select all
({1,0,1}, {1,0,1,0}, {1,0,1,0,0})

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
why WA?
It seems right but I can't find the bug.
Code: Select all
#include <iostream>
#define MAXN 10000
using namespace std;
long long t, cc, a, b, c, m, n, i, r, res;
long long x[MAXN];
long long s[MAXN];
long long mod[MAXN];
int main()
{
cin >> t;
for (cc=0; cc<t; cc++)
{
cin >> a >> b >> c >> m >> n;
x[0] = a;
for (i=1; i<n; i++)
x[i] = ((x[i1] * b + c) % m) + 1;
s[0] = x[0];
for (i=1; i<n; i++)
s[i] = (s[i1] + x[i]) % m;
for (i=0; i<MAXN; i++)
mod[i] = 0;
for (i=0; i<n; i++)
mod[s[i] % m]++;
res = 0;
for (i=0; i<m; i++)
res += (mod[i]*(mod[i]1) / 2);
cout << "Case " << cc+1 << ": " << res << endl;
}
return 0;
}
paulmcvn wrote:First, generate the sequence x like the problem description
Then, generate the sequence s,
where s = x[0] + x[1] + ... x
While computing, you can set s = (s[i1] + x) % m; , because we only deal with the remainder modulo m
For each 0<=r<m, count the number of s, so that s % m = r
That means, you have to iterate through s, and set
mod[s % m]++;
Moreover, set mod[0]++;
Then, the result is sum ( mod*(mod[i]  1) div 2, i=0..m1)
That's simply because each subsequence can be represented as s[i]  s[j] for some i,j.
Would you please give a detailed explanation about sum ( mod[i]*(mod[i]  1) div 2, i=0..m1) formula? I can't get it
per aspera ad astra

 Experienced poster
 Posts: 105
 Joined: Wed May 25, 2005 7:23 am
First, generate the sequence x like the problem description
Then, generate the sequence s,
where s = x[0] + x[1] + ... x
While computing, you can set s = (s[i1] + x) % m; , because we only deal with the remainder modulo m
For each 0<=r<m, count the number of s, so that s % m = r
That means, you have to iterate through s, and set
mod[s % m]++;
Moreover, set mod[0]++;
Then, the result is sum ( mod*(mod[i]  1) div 2, i=0..m1)
That's simply because each subsequence can be represented as s[i]  s[j] for some i,j.[/quote]
Would you please give a detailed explanation about sum ( mod[i]*(mod[i]  1) div 2, i=0..m1) formula? I can't get it
Then, generate the sequence s,
where s = x[0] + x[1] + ... x
While computing, you can set s = (s[i1] + x) % m; , because we only deal with the remainder modulo m
For each 0<=r<m, count the number of s, so that s % m = r
That means, you have to iterate through s, and set
mod[s % m]++;
Moreover, set mod[0]++;
Why should this be done ?
Then, the result is sum ( mod*(mod[i]  1) div 2, i=0..m1)
That's simply because each subsequence can be represented as s[i]  s[j] for some i,j.[/quote]
Would you please give a detailed explanation about sum ( mod[i]*(mod[i]  1) div 2, i=0..m1) formula? I can't get it
I don't understand this quite why it should be done. rationale behind this