結果
問題 | No.695 square1001 and Permutation 4 |
ユーザー |
|
提出日時 | 2018-06-10 23:29:05 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,263 ms / 7,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 762 ms |
コンパイル使用メモリ | 120,704 KB |
実行使用メモリ | 41,784 KB |
最終ジャッジ日時 | 2024-07-22 19:34:04 |
合計ジャッジ時間 | 7,129 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
#include <vector>#include <algorithm>#include <cstdio>using namespace std;int solve(int n,int M,const vector<int> &x){int m=n/2,r=0;vector<int> v(n-m);v[0]=1;for(int i=1;i<n-m;i++)for(auto &e:x){if(e<=i)v[i]=(v[i]+v[i-e])%M;}for(auto &e:x)for (int j = 0; 2 * j < n; j++) {if (2 * (j + e) >= n && j + e < n) {r = (r + 1LL * v[j] * v[n - j - e - 1]) % M;}}return r;}long long pow(long long x,long long y,long long mod){long long z=1;for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;}int main(){int n,m;scanf("%d%d",&n,&m);vector<int>x(m);for(int i=0;i<m;i++)scanf("%d",&x[i]);int M1=168647939,M2=592951213;int R1=solve(n,M1,x),R2=solve(n,M2,x);long long Rm=(R2-R1+M2)*pow(M1,M2-2,M2)%M2;printf("%lld\n",1LL*Rm*M1+R1);}