TOPIC

5% alguém sabe pq?

Felipe asked 1 year ago

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010
#define mod 1000000009
#define ll long long

ll fat[MAXN];

void fatorial(){
  fat[0] = 1;
  for(int i = 1; i < MAXN; i++){
    fat[i] = ((ll) i*fat[i - 1])%mod;
  }
}

int main() {
  fatorial();
  int n;
  while(cin >> n and n){
    ll sum = 0;
    for(int i = 1; i < n - 1; i++){
      sum = (sum + (i*(n - i - 1))%mod);
    }
    cout << (sum*fat[n - 3])%mod << endl;
  }
  return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Felipe replied 1 year ago

    thanks, feodorv

  • feodorv replied 1 year ago

    You can try the following input:

    100000
    0

    The correct answer is 168441616, your solution gives 283201035. You can fix your solution:

    1.  sum = (sum + ((ll) i*(n - i - 1))%mod);
    2. sum %= mod; after summing (line #25)

    Also your solution is O(n), the problem can be solved in O(1).