NP(np)

Time Limit:1000ms Memory Limit:64MB

Question description

lyk likes to study some difficult problems, such as NP issues. 
 This time it encountered another tricky NP problem. The problem is like this: there are two numbers n and p, find the step of n 
 The result of picker p. 
 LYK thinks all NP problems are algorithm without polynomial complexity, so it intends to ask for help to participate in NOIP 
 You, help LYK!

Input format (np.in)

Input a line of two integer n, p.

output format (np.out)

Output a line of an integer to represent the answer.

Input sample

3 4

output sample

2

data range

For 20%data: n, p <= 5. 
 For 40%data: n, p <= 1000. 
 For 60%data: n, p <= 10000000. 
 For 80%data: n <= 10^18, P <= 10000000. 
 For another 20%data: n <= 10^18, P = 10000007. 
 Of these, 50%of the data meets n> = p.

Thinking:

Blocking Table 
 All K!, Where K Mod 10000000 = 0. Find the known answer directly when you ask, and you can find the answer without more than 100,000.

code:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
long long n,p;
long long now;
const int a[100]={
   682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116};
const int MOD=1000000007;
int main()
{
    freopen("np.in","r",stdin);
    freopen("np.out","w",stdout);
    cin>>n>>p;
    if (p==1000000007)
    {
        if (n>=p) {
   puts("0"); return 0;}if (n<10000000) now=1; else now=a[n/10000000-1];
        for (int i=n/10000000*10000000+1; i<=n; i++) now=now*i%MOD;
    } else
    {
        now=1;
        if (n>=p) now=0; else for (int i=1; i<=n; i++) now=now*i%p;
    }
    cout<<now<<endl;
    return 0;
}

Look at the program writing results (Program)

Time Limit:1000ms Memory Limit:64MB

Description

lyk is currently preparing NOIP2017's preliminary round. What is the least good at is to see the program and write the results, so it desperately 
 Practicing. 
 This time it gets such a program: 
 Pascal: 
 Readln (n); 
 for i: = 1 to n do read (a [i]); 
 For I: = 1 to n do for j: = 1 to n do for k: = 1 to n do for l: = 1 to n down 
 if (a [i] = a [j]) and (a [i] <a [k]) and (a [k] = a [l]) then ans: = (ang 1) MOD 1000000007; 
 writeln (ANS); 

 C ++: 
 scanf ("%d", & n); 
 for (i = 1; i <= n; i ++) scanf ("%d", & a [i]); 
 For (i = 1; i <= n; i ++) for (j = 1; j <= n; j ++) for (k = 1; k <= n; k ++) for (l = 1; l <= n; L ++) 
 if (a [i] == a [j] && a [i] <a [k] && a [k] == a [l]) ans = (ang 1)%1000000007; 
 Printf ("%d \ n", ANS); 
 LYK knows all the input data, and it wants to know how much this program runs.

Input format (Program.in)

The first line of the number n, the second line n, represent AI.

output format (program.out)

A number indicates the answer.

Input sample

4
1 1 3 3

output sample

4

Data range

For 20%data n <= 50. 
 For 40%data n <= 200. 
 For 60%data n <= 2000. 
 For 100%data n <= 100000, 1 <= AI <= 1000000000. 
 Among them, 50%of the number of AIs with different data <= 10 is evenly distributed, and the number of AIs with different data of 50%of the data> = n/10.

• –

Thinking:

The principle of multiplication is used 
 Sort the AI first. 
 Let f [i] represent the same AI pair in 1 ~ i. 
 For the position of all AI! = A {i+1}, the f [i]*g*(g-1)/2 is added into the answer. G represents how much number exists = a {i+1}. 
 Time complexity NLGN.

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long ans,f[100005];
int i,n,a[100005],sum;
const int MOD=1000000007;
int cmp(int i,int j) {
   return i<j;}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp); sum=1; f[1]=1;
    for (i=2; i<=n; i++)
    {
        f[i]=f[i-1];
        if (a[i]==a[i-1])
        {
            f[i]=f[i]-1ll*sum*sum; sum++;
            f[i]=f[i]+1ll*sum*sum;
            f[i]%=MOD;
        } else {
   sum=1; f[i]++;}
    }
    sum=0;
    for (i=n; i>=2; i--)
    {
        if (a[i]==a[i+1]) sum++; else sum=1;
        if (a[i]!=a[i-1]) ans=(ans+f[i-1]*sum%MOD*sum)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}

Select numbers (Select)

Time Limit:3000ms Memory Limit:64MB

Title description

lyk found a matrix of N*M. There are some numbers on this matrix. 
 The number is AI, J. 
 Because it was AK's preliminary round of NOIP2016, it seemed very boring recently, and I thought of a way to entertain and entertain it. 
 The game it thinks is like this: every time you choose one or a column, the happiness value it gets will be this line or a column 
 The sum of numbers. After that, it subtracted the number of the line or on the column (may be turned into negative numbers later). So, repeat K K 
 Second, the sum of the happiness it gets will be its NOIP2016 rematch. 
 Lyk certainly wants its RP value to be as high as possible, so it will help you.

Input format (Select.in)

The first line of 4 numbers n, m, k, p. 
 Next N line M column, representing AI, J.

output format (Select.out)

Output a line represents the maximum RP value.

Input sample

2 2 5 2
1 3
2 4

output sample

11

Data range

A total of 10 sets of data. 
 For groups 1, 2 data n, m, k <= 5. 
 For the third group of data K = 1. 
 For the 4th group of data p = 0. 
 For groups 5,6 data n = 1, m, k <= 1000. 
 For group 7,8 data n = 1, m <= 1000, k <= 1000000. 
 For all data 1 <= n, m <= 1000, K <= 1000000, 1 <= AI, J <= 1000, 0 <= P <= 100.

Sample Explanation

Choose the second column for the first time, the second line of the second line, the third time the first line, the second line of the second line, the fifth 
 Select the first line, the happiness value is 7+4+2+0+-2 = 11.

Thinking:

The order of choice is irrelevant. Assuming that we chose line X, then the K-X column must be selected. 
 Let f [i] indicate the maximum sum to choose I. Consider how to find all f [i]. 
 This is obviously greedy. Record the sum of all lines. Just use the big roots to maintain. 
 Let G [i] indicate the maximum selection of I column. Known F and G. 
 The answer is Max {f [i]+g [k-i] -I*(k-I)*p).

code:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1000005;
long long ans,s1[N],s2[N],p1[N],p2[N];
int k,n,m,i,j,p,A;
int cmp(int i,int j) {
   return i<j;}
int main()
{
    freopen("select.in","r",stdin);
    freopen("select.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
    {
        scanf("%d",&A);
        s1[i]+=A; s2[j]+=A;
    }
    make_heap(s1+1,s1+n+1,cmp);
    make_heap(s2+1,s2+m+1,cmp);
    for (i=1; i<=k; i++)
    {
        p1[i]=p1[i-1]+s1[1];
        pop_heap(s1+1,s1+n+1,cmp);
        s1[n]-=p*m;
        push_heap(s1+1,s1+n+1,cmp);
        p2[i]=p2[i-1]+s2[1];
        pop_heap(s2+1,s2+m+1,cmp);
        s2[m]-=p*n;
        push_heap(s2+1,s2+m+1,cmp);
    }
    ans=1ll*-1000000000*1000000000;
    for (i=0; i<=k; i++) {ans=max(ans,p1[i]+p2[k-i]-1ll*i*(k-i)*p);}
    cout<<ans;
    return 0;
}