1471 Spion

[•Teodor94]

Aici puteti discuta despre problema Spion.

[•fluture.godlike]

Am aflat, multumesc!

[•dey44and]

Salut! Problema asta ma nelamureste...
Initial am facut o functie care rezolva prima cerinta si declaram variabilele global, si pe ultimele 2 teste de la prima cerinta luam time limit exceed, iar acum dupa ce fac totul in main la prima cerinta totul merge ok. Insa la a doua nu imi afiseaza bine, am gresit la proprietatile modulului?

#include <fstream>
#include <cstring>
#define mod 100003

using namespace std;
typedef long long ll;

ifstream in("spion.in");
ofstream out("spion.out");

ll exp_rapid(ll a, ll b)
{
    if(b==0) return 1;
    if(b==1) return a % mod;
    if(b%2==1) return (a * exp_rapid(a, b - 1)) % mod;
    return exp_rapid(a * a % mod, b/2) % mod;
}

int main()
{
    int cerinta;
    char traseu[100002];
    int casuta = 1;
    in>>cerinta;
    in.ignore();
    in.get(traseu,100003);
    for(unsigned i = 0; i < strlen(traseu); i++)
        if(traseu=='E')
            casuta++;
    if(cerinta==1)
        out << casuta;
    else
    {
        int total = 1, est = 1, vest = 1, fin;
        int fact = strlen(traseu);
        int fact2 = casuta - 1;
        int fact3 = fact - casuta + 1;
        //out << fact << " " << fact2 << " " << fact3 << "\n";
        for(int i = 2; i <= fact; i++)
            total=(total*i)%mod;
        for(int i = 2; i <= fact2; i++)
            est=(est*i)%mod;
        for(int i = 2; i <= fact3; i++)
            vest=(vest*i)%mod;
        est = exp_rapid(est, mod - 2) % mod;
        vest = exp_rapid(vest, mod - 2) % mod;
        fin = total*est%mod*vest%mod;
        out << fin;
    }
    return 0;
}

L.E. Am rezolvat pana la urma, am folosit la toate variabilele tipul long long. 

[•dey44and]

Si totusi, am observat ca time limit exceed luam din cauza faptului ca declaram global variabila pe care o incrementam, casuta. Dupa ce am declarat local, problema s-a rezolvat. Imi poate explica cineva de ce.. sincer.. imi da batai de cap problema asta.. imi ramane asta neclar.