重温了这道cdq+FFT
讲白了就是不断对 dp[l~mid] 和 sh[1~r] 进行fft 得到 dp[mid+1~r]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5+5;

const int MOD = 313;

int N;

int sh[MAXN], dp[MAXN];

int ans;

/****************FFT*************/

int A[MAXN<<2], B[MAXN<<2], C[MAXN<<2];

struct FFTSOLVE {

    int pos[MAXN<<2];

    struct comp {

        double r , i ;

        comp ( double _r = 0 , double _i = 0 ) : r ( _r ) , i ( _i ) {}

        comp operator + ( const comp& x ) {

            return comp ( r + x.r , i + x.i ) ;

        }

        comp operator - ( const comp& x ) {

            return comp ( r - x.r , i - x.i ) ;

        }

        comp operator * ( const comp& x ) {

            return comp ( r * x.r - i * x.i , i * x.r + r * x.i ) ;

        }

        comp conj () {

            return comp ( r , -i ) ;

        }

    } A[MAXN<<2] , B[MAXN<<2] ;

    const double pi = acos ( -1.0 ) ;

    void FFT ( comp a[] , int n , int t ) {

        for ( int i = 1 ; i < n ; ++ i ) if ( pos[i] > i ) swap ( a[i] , a[pos[i]] ) ;

        for ( int d = 0 ; ( 1 << d ) < n ; ++ d ) {

            int m = 1 << d , m2 = m << 1 ;

            double o = pi * 2 / m2 * t ;

            comp _w ( cos ( o ) , sin ( o ) ) ;

            for ( int i = 0 ; i < n ; i += m2 ) {

                comp w ( 1 , 0 ) ;

                for ( int j = 0 ; j < m ; ++ j ) {

                    comp& A = a[i + j + m] , &B = a[i + j] , t = w * A ;

                    A = B - t ;

                    B = B + t ;

                    w = w * _w ;

                }

            }

        }

        if ( t == -1 ) for ( int i = 0 ; i < n ; ++ i ) a[i].r /= n ;

    }

    void mul ( int *a , int *b , int *c ,int k) {

        int i , j ;

        for ( i = 0 ; i < k ; ++ i ) A[i] = comp ( a[i] , b[i] ) ;

        j = __builtin_ctz ( k ) - 1 ;

        for ( int i = 0 ; i < k ; ++ i ) {

            pos[i] = pos[i >> 1] >> 1 | ( ( i & 1 ) << j ) ;

        }

        FFT ( A , k , 1 ) ;

        for ( int i = 0 ; i < k ; ++ i ) {

            j = ( k - i ) & ( k - 1 ) ;

            B[i] = ( A[i] * A[i] - ( A[j] * A[j] ).conj () ) * comp ( 0 , -0.25 ) ;

        }

        FFT ( B , k , -1 ) ;

        for ( int i = 0 ; i < k ; ++ i ) {

            c[i] = ( long long ) ( B[i].r + 0.5 );

        }

    }

}boy;

void cdq(int l,int r) {

    if(l == r) {

        dp[l] = (dp[l] + sh[l]) % MOD;

        return;

    }

    int mid = (l+r)>>1;

    cdq(l,mid); 

    int l1 = 0, l2 = 0;

    for(int i = l; i <= mid; ++i) A[l1++] = dp[i];

    for(int i = 1; i <= N; ++i) {

        if(i+l > r) break;

        B[l2++] = sh[i];

    }

    int len = 1;

    while(len < l1*2 || len < l2*2) len <<= 1;

    for(int i = l1; i < len; ++i) A[i]=0;

    for(int i = l2; i < len; ++i) B[i]=0;

    boy.mul(A,B,C,len);

    for(int i = mid+1; i <= r; ++i) {

        dp[i] = (dp[i]+C[i-l-1]) %MOD;

    }

    cdq(mid+1,r);

}

int main(){

    while(~scanf("%d",&N)) {

        memset(dp,0,sizeof(dp));

        if(N == 0) break;

        for(int i = 1; i <= N; ++i) {

            scanf("%d",&sh[i]); sh[i] %= MOD;

        }

        cdq(1,N);

        printf("%d\n",dp[N]);

    }

    return 0;

}