Expert.
Put your skills to the test.

Problem summary

A plan on N labeled activities is any set of ordered preferences (x,y), x != y. Preferences are transitive: a directed path also requires its first activity before its last. Count plans for which the largest set of activities that can be ordered without contradicting any preference has size exactly K. Return the count modulo 12289.

Constraints

1 <= N <= 650; 1 <= K <= N; 8 seconds; 1024 MB.

Worked example

Original statement sample, using the documented local driver for grader tasks.

4 3

774

Solution analysis

1. Represent preferences by a simple directed graph. Two vertices in one strongly connected component cannot both be chosen: each precedes the other. Conversely, choose one vertex from every SCC and order the condensation DAG topologically. Therefore the requested maximum is exactly the number of SCCs. Prerequisites are SCCs, labeled counting, inclusion-exclusion, and the number-theoretic transform (NTT).
2. Let G[n,k] be the number of graphs with k SCCs divided by n! modulo 12289. Let H[n,s] count, also divided by n!, graphs consisting of s SCCs with no edges between different components. Then H[n,s] = (1/s) sum_t G[t,1] H[n-t,s-1]. Division by s removes the choice of a distinguished component. H[0,0]=G[0,0]=1. For s>=2, only already computed smaller graph sizes are used.
3. Every nonempty condensation DAG has at least one source SCC. Inclusion-exclusion over selected source components gives G[n,k] = sum_{c=1..n} 2^(c(n-c)) sum_s (-1)^(s+1) H[c,s] G[n-c,k-s]. There are no edges into the selected sources; each of their c vertices may independently have an edge to each remaining vertex. Selected source SCCs have no edges between them. For k>=2 the c=n term is known. Determine G[n,1] by subtracting the other SCC counts from 2^(n(n-1))/n!, the normalized count of all digraphs.
4. For fixed c, the inner sum is a polynomial convolution. Cache NTTs of G[c,*] and signed H[c,*]. For a new n, accumulate all products in frequency space and apply just one inverse NTT. Use a transform length strictly greater than n: every product has degree at most n, so no cyclic wraparound occurs. Rebuild older cached transforms only when this power-of-two length doubles. The prime 12289 supports the needed lengths and primitive root 11.
5. For N=2, all four possible edge sets split into three DAGs with two SCCs and the bidirectional graph with one SCC. Thus count_plans(2,2)=3. For N=4,K=3, the recurrence returns 774. Multiplication by N! restores labeled counts at the end.

Why it works

SCC condensation proves the equivalence between the scheduling maximum and SCC count. H counts unordered independent components by distinguishing one and dividing by their number. Source-SCC inclusion-exclusion counts every nonempty graph exactly once because a DAG with q sources contributes sum_{s=1..q} (-1)^(s+1) C(q,s)=1. Normalization cancels binomial label choices. The recurrence and total-count identity therefore determine every graph count; NTT changes only how its exact modular convolution is evaluated.

Watch out. Count SCCs, not merely acyclic induced subsets ignoring transitive paths. Source components must have no edges between them. Include the c=n term with its sign. Use NTT length > n, not >= n. Do not recompute one NTT for every pair of rows, which is unnecessarily expensive.

The judge expects count_plans without main. Compile with -DLOCAL for the stdin/stdout demonstration. No floating-point FFT or external library is used.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
namespace Plans{
const int mod=12289;
int power(int base,int exponent){
    int result=1;
    while(exponent>0){
        if(exponent&1){
            result=result*base%mod;
        }
        base=base*base%mod;
        exponent>>=1;
    }
    return result;
}
void transform(vector<int>&values,bool inverse){
    int size=(int)values.size();
    for(int i=1,j=0;i<size;++i){
        int bit=size>>1;
        while(j&bit){
            j^=bit;
            bit>>=1;
        }
        j^=bit;
        if(i<j){
            swap(values[i],values[j]);
        }
    }
    for(int length=2;length<=size;length*=2){
        int root=power(11,(mod-1)/length);
        if(inverse){
            root=power(root,mod-2);
        }
        for(int start=0;start<size;start+=length){
            int multiplier=1;
            for(int offset=0;offset<length/2;++offset){
                int first=values[start+offset];
                int second=values[start+offset+length/2]*multiplier%mod;
                values[start+offset]=(first+second)%mod;
                values[start+offset+length/2]=(first-second+mod)%mod;
                multiplier=multiplier*root%mod;
            }
        }
    }
    if(inverse){
        int inverseSize=power(size,mod-2);
        for(int&value:values){
            value=value*inverseSize%mod;
        }
    }
}
} // namespace Plans
int count_plans(int N,int K){
    using namespace Plans;
    vector<int>factorial(N+1,1);
    vector<int>inverseFactorial(N+1,1);
    vector<int>inverse(N+1,1);
    for(int i=1;i<=N;++i){
        factorial[i]=factorial[i-1]*i%mod;
        inverse[i]=power(i,mod-2);
    }
    inverseFactorial[N]=power(factorial[N],mod-2);
    for(int i=N;i>0;--i){
        inverseFactorial[i-1]=inverseFactorial[i]*i%mod;
    }
    vector<int>powersOfTwo(N*N+1,1);
    for(int i=1;i<=N*N;++i){
        powersOfTwo[i]=powersOfTwo[i-1]*2%mod;
    }
    // Divide counts on n labels by n!, so label choices become convolutions.
    vector<vector<int>>graphs(N+1,vector<int>(N+1));
    vector<vector<int>>independent(N+1,vector<int>(N+1));
    vector<vector<int>>graphTransform(N+1);
    vector<vector<int>>sourceTransform(N+1);
    graphs[0][0]=1;
    independent[0][0]=1;
    int length=1;
    auto cache=[&](int n){
        graphTransform[n].assign(length,0);
        sourceTransform[n].assign(length,0);
        for(int count=0;count<=n;++count){
            graphTransform[n][count]=graphs[n][count];
            if(count>0){
                sourceTransform[n][count]=
                    count%2?independent[n][count]:(mod-independent[n][count])%mod;
            }
        }
        transform(graphTransform[n],false);
        transform(sourceTransform[n],false);
    };
    for(int n=1;n<=N;++n){
        if(length<=n){
            while(length<=n){
                length*=2;
            }
            // Rebuild only at powers of two, not once per convolution.
            for(int previous=0;previous<n;++previous){
                cache(previous);
            }
        }
        for(int count=2;count<=n;++count){
            long long sum=0;
            for(int size=1;size<=n-count+1;++size){
                sum+=1LL*graphs[size][1]*independent[n-size][count-1];
            }
            independent[n][count]=(sum%mod)*inverse[count]%mod;
        }
        vector<int>coefficients(length);
        for(int frequency=0;frequency<length;++frequency){
            long long sum=0;
            for(int sourceSize=1;sourceSize<n;++sourceSize){
                sum+=1LL*powersOfTwo[sourceSize*(n-sourceSize)]*
                    sourceTransform[sourceSize][frequency]*graphTransform[n-sourceSize][frequency];
            }
            coefficients[frequency]=sum%mod;
        }
        transform(coefficients,true);
        int total=powersOfTwo[n*(n-1)]*inverseFactorial[n]%mod;
        for(int count=2;count<=n;++count){
            int signedIndependent=count%2?independent[n][count]:(mod-independent[n][count])%mod;
            graphs[n][count]=(coefficients[count]+signedIndependent)%mod;
            total=(total-graphs[n][count]+mod)%mod;
        }
        graphs[n][1]=total;
        independent[n][1]=total;
        cache(n);
    }
    return graphs[N][K]*factorial[N]%Plans::mod;
}
#ifdef LOCAL
int main(){
    int n;
    int k;
    cin>>n>>k;
    cout<<count_plans(n,k)<<'\n';
}
#endif